AGC031 B - Reversi (700)

B - Reversi

概要

長さNの正整数列Cが与えられる。この数列に以下の操作を好きなだけ行う。

• C[i] = C[j] (i < j)なら, C[i+1] = C[i+2] = ... =C[j-1] = C[i] (= C[j])とする

上の操作の結果出来上がる整数列の種類数を答えよ。(mod 10^9 + 7 して出力)

制約

1 ≦ N ≦ 2 * 10^5
1 ≦ C[i] ≦ 2 * 10^5

方針

大まかにはDPを使う。
dp[i] = i番目まで見たときの種類数 を考える。

注意点として例えばサンプル３
1 3 1 2 3 3 2
のように「1 3 1」⇒「1 1 1」にした後、これと独立に「2 3 3 2」⇒「2 2 2 2」とできること。
なので、ペアを見つけた場合はそのペアの前の数列の種類数を把握する必要がある。
逆にいうと、ある数字が出てきた場合、その数字の「前方ペアの直前までの種類数」(dp2)を把握しておき、その種類数を現在の種類数に足してゆけばよい。また、同時に「前方ペアの直前までの種類数」も更新する。
（ソースコード参照）

この実装法の注意点として、例えばサンプル３の「3 3」の部分では、2回目の3を用いて操作を行ってできる数列は、1回目の3を用いて操作を行ってできる数列と完全に一致する。よって、直前が同じ数字の場合は現在の種類数をそのまま維持し、「前方ペアの直前までの種類数」も更新しない。

解答

Submission #7828496 - AtCoder Grand Contest 031

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
const ll MOD = 1e9 + 7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	vector<int> c(n);
	rep(i, n) cin >> c[i];
 
	vector<ll> dp(n+1, 0);
	vector<ll> dp2(202020, 0);
	dp[0] = 1;
 
	rep(i, n){
		if(c[i-1] == c[i]){
			dp[i+1] = dp[i];
		}else{
			dp[i+1] = dp[i] + dp2[c[i]];
			dp[i+1] %= MOD;
 
			dp2[c[i]] += dp[i];
			dp2[c[i]] %= MOD;
		}
	}
 
	cout << dp[n] << endl;
 
}