AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）

　Gが解けなかったのは仕方ないとして、Eが解けないのはまずい。

コンテストへのリンク

コンテスト後のツイート

AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382） Eが解けずGは見ていない。
C 美味しさ何以上なら誰が食べるかを求め、二分探索
D 再帰。入れる数の最大値で絞る。
E 一回でx個増える確率を計算。0回の場合を除けば、あとはFFTをX回すれば良さそう→TLE。
F 遅延セグ木。

— titia (@titia_til) November 30, 2024

 E - Expansion Packs

　解説放送を途中まで見てAC。

　何度もやっているにもかかわらず「期待値DP」がまともにできていないことを反省。

　「一回でx枚レアを引く確率」はコンテスト中に問題なく求められていた。それを利用して、x回操作したとき、レアをy枚もっている確率をDPしようとしたのが筋が悪い。期待値をそのまま持つ方が自然で、それで答えが出せる。

　さらに、期待値DPといわれても立式できなかったのが情けない。

　DP[i]を、「残り枚数がi枚のとき、ゴールへ至る日数の期待値」と定義すれば、自然に期待値DPできる。