大手前プロコン 2019：D - FizzBuzz (FizzBuzz)

問題
解法
解答

問題

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

解法

以下の DP を考える．

dp(i, j, k) := 上から i 桁目まで決めて，今まで j 回発言し，上から i 桁目までの整数を 3 で割った余りが k であるときの，i + 1 桁目以降の通り数

遷移は i + 1 桁目に 0 ~ 9 を当てはめてみればよい．当てはめたあとの k を newK とおくと，newK == (k * 10 + l) % 3 (0 <= l <= 9) となる．newK が 3 で割り切れるとき，3 の倍数が構成できており，l == 0, 5 であるとき，5 の倍数が構成できている．構成出来た倍数と j + 1 回目の発言の内容が一致していれば dp(i + 1, j + 1, newK) に遷移すればよい．もし，3 の倍数でも 5 の倍数でもないときは dp(i + 1, j, newK) に遷移すればよい．O(NM)．