7K12 blog

猫でも分かる何か

CPSCO2019 Session1 D - Dessert Planning

f:id:tkr987:20200727003340p:plain

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()))

f:id:tkr987:20200727003435p:plain

Nが 10^{18}なので、DPで直接求めることは出来ない。したがって、数列の一般項からO(1)で答えを出すと予想する。dp[i][d] := i回目に食べた菓子がdだったときの組み合わせ、と定義する。 i mod 3 = 0 のとき dp[i][cake] = 0 になることに注意しつつ、DPを使ってシミュレーションすると組み合わせが8, 40, 200, 1000, ...と増加することが分かる。

この数列をOEISで検索すると一般項  \frac{8}{5} \times 5^n が得られる。

https://oeis.org/A128625