nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume10 問題リンク Ben Toh 解法 DPです。 dp[ n ]: n日間に得られる弁当の個数の期待値 の表を埋めて解きます。 n日間の期間があり、初日から連続してk日間弁当を獲得できている場合を考えます、またこの状態になる確率をp、次の弁当獲得確率をwinとします。ここで、p*(1-win)の確率で弁当獲得に失敗します。そしてk+2日目からは残り日数n-k-1の場合と全く同じ状態遷移図となるのでdp[n-k-1]の結果が使えます。つまり dp[ n ] += p*(1-win) * (k + dp[max{0, n-k-1}]) となります。このkを1〜nまで続け、最後に、連続n日間弁当を獲得し… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20120430%2F1335746061" title="AOJ1056 Ben Toh - nanikakaのAOJ航海日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-04-30 09:34:21 rich https://nanikaka.hatenadiary.org/entry/20120430/1335746061 1.0 100%