AGC 031 B - Reversi - ykmakuのブログ

このAGCは引越の疲れで参加できてなかった...

問題

解法

手で実験してみるとDPぽいな〜と思ったのでDPを考えます.
$dp[i] = a[0],\dots,a[i-1]$ に対する塗り方の個数
とします.
色が切り替わるときに注目します.
f:id:ykmaku:20190317021023p:plain
いま，j+1番目の石を見ているとしましょう.
さらにj+1番目の石の色と同じ色の石で，(j以下で)j+1に最も近いものの位置をiとします.
このとき，iとj+1番目の石を選んで操作を行ったときの色の塗り方は $a[0],\dots,a[i-1]$ の塗り方の個数なので $dp[i]$ です.
iとj+1番目の石に対して操作を行わなかったときの色の塗り方は $dp[j]$ です.
したがって $dp[j+1] = dp[i] + dp[j]$ であることが分かります.

各色に対して，１番右側にあるものの位置(またはそのdpの値)を記憶しておけば，j+1番目の石の色と同じ色の石で，(j以下で)j+1に最も近いものの位置(またはそのdpの値)は $O(1)$ で求められます.
結局，この問題は $O(N)$ で解けることになります.

#include <iostream>
#include <vector>

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;
const ll MAXN = 2*1e5+1;

int main()
{
	ll n;
	cin>>n;
	vector<ll> c(n);
	for(int i = 0; i < n; i++){
		cin>>c[i];
	}
	vector<ll> dp(MAXN,0);
	dp[c[0]]=1;
	for(int i = 1; i < n; i++){
		if(c[i]!=c[i-1]){
			dp[c[i]] = (dp[c[i]]+dp[c[i-1]]) % mod;
		}
	}

	cout << dp[c[n-1]] << endl;

	return 0;
}