FizzBuzz (FizzBuzz) [大手前プロコン 2019 D]

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d

前提知識

• 桁DP

解説

https://atcoder.jp/contests/otemae2019/submissions/6931592

まずmod10⁹+7なので、とりあえずDPを疑おう。
今回は桁数が大きく、かつ、上から決めていくので、桁DPを疑おう。
倍数によって処理を変えているようなので、modをindexとして使えばよさそう。
いつもの桁DPが思い浮かぶので、やってみるとできそう。
dp[idx][mo] := idx桁目まで確定していて、%15するとmoとなる数の組み合わせ
15の剰余を見れば、状況がまとめられそうなので、indexに入れる。
idx単位でDP更新後、条件を満たさないものは0にするようにして更新していく。

あとは、いつ発言したかであるが、これも何回発言済みかというのをindexに入れれば問題ない。
dp[idx][spoken][mo] := idx桁目まで確定していて、spoken回発言済みで、%15するとmoとなる数の組み合わせ
先頭が0は許されないので、注意。
あと、配列テーブルが大きいので、一応idxはmod2で使いまわすようにして節約した。
あと、文字列そのままで判定するとTLEするので、大丈夫な値を前計算しておこう。

2019.09.21 追記 教えていただいた、より良い回答
%15でDPテーブルは持っているが、最後の桁が0か5であれば5の倍数かどうかは判定できるので、抽象化して覚えておく値は%3だけで十分。
なので、倍数判定をするときに%3でDPでは持って、5の倍数かどうかは選択した数が0,5であるかを確認することで、
メモリ使用量、ループの数を1/5にすることができる。

int N, M; string S[1010];
bool ok[1010][15];
mint dp[2][1010][15];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> S[i];

    rep(i, 0, M) {
        if (S[i] == "Fizz") ok[i][3] = ok[i][6] = ok[i][9] = ok[i][12] = true;
        else if (S[i] == "Buzz") ok[i][5] = ok[i][10] = true;
        else if (S[i] == "FizzBuzz") ok[i][0] = true;
    }
    rep(mo, 0, 15) if (mo % 3 != 0 and mo % 5 != 0) ok[M][mo] = true;

    dp[0][0][0] = 1;
    rep(_idx, 0, N) {
        int idx = _idx % 2;
        int idx2 = 1 - idx;

        rep(spoken, 0, M + 1) rep(mo, 0, 15) dp[idx2][spoken][mo] = 0;

        rep(spoken, 0, M + 1) {
            rep(mo, 0, 15) rep(nxt, 0, 10) {
                if (_idx == 0 and nxt == 0) continue;

                int mo2 = (mo * 10 + nxt) % 15;

                if (spoken == M) {
                    if (ok[M][mo2]) dp[idx2][spoken][mo2] += dp[idx][spoken][mo];
                }
                else {
                    if (ok[M][mo2]) dp[idx2][spoken][mo2] += dp[idx][spoken][mo];
                    if (ok[spoken][mo2]) dp[idx2][spoken + 1][mo2] += dp[idx][spoken][mo];
                }
            }
        }
    }

    mint ans = 0;
    rep(mo, 0, 15) ans += dp[N % 2][M][mo];
    cout << ans << endl;
}