AGC 031 B - Reversi

AGC 031 B - Reversi に関連する、区間に分割する DP についてのメモを残します。

参考

区間に分割する DP については、これらの記事が分かりやすいです。

• AtCoder AGC 031 B - Reversi (700 点) - けんちょんの競プロ精進記録
• Reversi [AtCoder Grand Contest 031 B] - はまやんはまやんはまやん

区間に分割する DP

• 問題 : AGC 031 B - Reversi

左から 個の石の色の列としてありうるものの個数

とし、 とする。
下図は、入力例 2 の において、 への遷移を表したものである。

(今後、追記予定)

実装

解説放送 も参考にして実装しました。

#include <bits/stdc++.h>
using namespace std;

int main() {
  const int MOD = 1000000007;
  int N; cin >> N;
  vector<int> C;
  int tmp = -1;
  // 同じ数字が連続している箇所をなくす
  for (int i = 0; i < N; i++) {
    int c; cin >> c;
    if (c == tmp) continue;
    C.push_back(c);
    tmp = c;
  }
  int L = C.size();
  vector<int> dp(L+1), acc(200010);
  dp.at(0) = 1;
  for (int i = 0; i < L; i++) {
    // 塗りかえない
    dp.at(i+1) = (dp.at(i+1) + dp.at(i)) % MOD;
    // [x, i] を塗りかえる
    dp.at(i+1) = (dp.at(i+1) + acc.at(C.at(i))) % MOD;
    acc.at(C.at(i)) = (acc.at(C.at(i)) + dp.at(i)) % MOD;
  }
  cout << dp.at(L) << endl;
}