J - Sushiで期待値DPを掴んだ気がする

Quiz

https://atcoder.jp/contests/dp/tasks/dp_j

AC

https://atcoder.jp/contests/dp/submissions/8788822

参考

• けんちょんさん https://qiita.com/drken/items/03c7db44ccd27820ea0d#j-%E5%95%8F%E9%A1%8C---sushi
  • しかし、＋１の部分がよく分からなかった
• そこで、tsutajiroさん
  • http://compro.tsutaj.com/archive/180220_probability_dp.pdf

• サイコロの期待値DPで感覚を掴む
• 上記画像の最後で書かれている、
  • Σ（Es+x + 1) / 6
  • これは+1部分を外に出すと
  • Σ（Es+x)/6 + 1
  • となり、けんちょんさんのと同じ形になる
• （遷移元）＝（遷移先）＋１
• 今回のSushiに当てはめると、下記のようになる

• あとはけんちょんさんの通り、式変形で
• dp[i, j, k] = dp[(i, j, kがより小さい)]
• の形にしてメモ化再帰すればいい

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～