Chain Contestant [AtCoder Beginner Contest 215 E]

https://atcoder.jp/contests/abc215/tasks/abc215_e

前提知識

• bitDP

解説

https://atcoder.jp/contests/abc215/submissions/25245742

この問題はbitDPの応用問題となる。
とりあえずmod数え上げなので、DPがまず第一候補として挙がってくる。
コンテストの種類ごとでまとまりになっている必要があるので、以前やり終わったコンテストは利用できないということで、
コンテストに出たか出てないかという所でbitDP感がするし、コンテストも10種類ということでかなりそれっぽい。

bitDPについては説明しないので、理解してない場合はどこかで学習してきてほしい。

DP

正直、以下のDPテーブルが作れていればほぼ回答できているようなものである。

dp[i][msk][lst] :=
i回目のコンテストまで出場するかを決定していて、
出場済みコンテストの状況がmskで、
最後に出たコンテスト種類がlstである
場合の組み合わせ

mskだけだと条件判定に必要な連続で同じコンテストに出ているかの判定ができないので、最後にどのコンテストに出たかを
状態として含める必要がある部分が特徴的だが、bitDPではよく見られる条件。

どうやってこのテーブルを出したかという部分は何とも言えないが、必要そうな

• いつもの何回目までか
• コンテストに出たか出ないかを持っておく必要がある
• 条件判定には最後に出たコンテストの情報が必要

という部分をまとめ上げて、制約を確認すると問題なかったから、遷移を考えると解けたという流れになる。

遷移

dp[i][msk][lst]からの遷移で考えると、

• コンテストに出ない dp[i][msk][lst] -> dp[i + 1][msk][lst]
• コンテストに出る
  • 出るが、mskに含まれていてlstと違ったら出れないので遷移できない
  • そうじゃない場合は出れるので、 dp[i][msk][lst] -> dp[i + 1][msk | (1<<nxt)][nxt]

mskに状態を追加する場合は、or計算で追加すると遷移分けをしなくてもよくなるので便利。

int N; string S;
mint dp[1010][1 << 10][11];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    dp[0][0][10] = 1;
    rep(i, 0, N) rep(msk, 0, 1 << 10) rep(lst, 0, 11) if (dp[i][msk][lst] != 0) {
        dp[i + 1][msk][lst] += dp[i][msk][lst];
        
        int nxt = S[i] - 'A';
        if ((msk & (1 << nxt)) && lst != nxt) continue;
        dp[i + 1][msk | (1 << nxt)][nxt] += dp[i][msk][lst];
    }

    mint ans = 0;
    rep(msk, 0, 1 << 10) rep(lst, 0, 10) ans += dp[N][msk][lst];
    cout << ans << endl;
}