人権なし

競プロで解いた問題や開発の進捗などの記録です

大手前プロコン 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).

解答

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

f:id:babcs2035:20190805144356p:plain