https://atcoder.jp/contests/cpsco2019-s1/submissions/15476330
- DPでシミュレーションして数列の一般項を求める
- 初期値は dp[0][0] = dp[0][1] = 1
- 繰り返しは rep(i, 1, 3 * N)
- 更新は dp[i][0] += (dp[i - 1][1] + dp[i - 1][2]); など
- 出力は Sum(all(dp.back()))
Nがなので、DPで直接求めることは出来ない。したがって、数列の一般項からO(1)で答えを出すと予想する。dp[i][d] := i回目に食べた菓子がdだったときの組み合わせ、と定義する。 i mod 3 = 0 のとき dp[i][cake] = 0 になることに注意しつつ、DPを使ってシミュレーションすると組み合わせが8, 40, 200, 1000, ...と増加することが分かる。
この数列をOEISで検索すると一般項 が得られる。
