Reversi [AtCoder Grand Contest 031 B]

https://atcoder.jp/contests/agc031/tasks/agc031_b

前提知識

• 動的計画法更新最適化（累積和）

解説

https://atcoder.jp/contests/agc031/submissions/4597345

まず、もともとの数列で同じ色の石が連続していても数え上げには影響が無いので、圧縮しておく。
（自分の実装では一旦ランレングス表現にしているが、どうやってもいい）
　
この状態でDPをする。
dp[i] := i番目の石まで塗り替えが終わっている場合の組合せ
i+1番目の石の色がcだったとする。
すると、i+1番目の石までの塗り替えを考えると、

• i+1番目の石には何もしない
• i+1番目以前の石で色がcのものと組合せて塗り替える

という選択が考えられる。
前者の操作は普通にdp[i + 1] += dp[i]である。
　
後者の説明のために、i+1番目以前で色がcの石の添字をj[0], j[1], j[2], ...とする。
i+1番目とj[0]番目で操作を行うと、dp[i + 1] += dp[ j[0] - 1]となる。
なので、dp[i + 1] += dp[ j[0] - 1] + dp[ j[1] - 1] + ... となる。
これはいかにもメモ化できそうな感じがある。
dp[i + 1] += (これまでの色がcの石の1つ前のDPの値の総和)
といえるので、
sm[c] := これまでの色がcの石の1つ前のDPの値の総和
として、メモっておこう。

int NN; vector<int> CC;
mint sm[201010];
mint dp[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> NN;
    rep(i, 0, NN) {
        int c; cin >> c;
        CC.push_back(c);
    }
 
    auto C = runLengthEncoding(CC);
    int N = C.size();
 
    dp[0] = 1;
    rep(i, 0, N) {
        int c = C[i].first;
        dp[i + 1] += sm[c] + dp[i];
        sm[c] += dp[i];
    }
    cout << dp[N] << endl;
}