ABC189F.txt

【解説】ABC-189-F Sugoroku2

　注：本解説には計算誤差に関する説明はありません。


《問題ページ》
https://atcoder.jp/contests/abc189/tasks/abc189_f


《解説》
　まず「振り出しに戻る」マスが M 個以上連続する部分がある場合はクリア不可能なので、あらかじめ判定してそのようなケースは除外しておきます。

　マス A_1, ..., A_K の「振り出しに戻る」を「偽のゴール」、マス [N, N+M) を「真のゴール」とし、これらを合わせて「ゴール」と呼ぶことにします。そして、「マス 0 からスタートしていずれかのゴールに到達したら終了」というゲームを「部分ゲーム」と呼ぶことにします。
　部分ゲームでの「マス i に止まる確率 P_i」と「マス i に止まるまでのターン数（止まらない場合は 0）の期待値 E_i」を計算します。これは配るＤＰでできます。具体的には、まず P_0 = 1 とし、ゴールではないマス i に対して昇順に
　　　　P_{i in [i+1, i+M]} += P_i / M
　　　　E_{i in [i+1, i+M]} += (E_i + P_i) / M
とすればよいです（ただしこれを愚直にやると遅いので、imos 法やセグメントツリーなどで高速化します）。
　ここで、
　　　　P_偽 := sum_{i: 偽のゴール} P_i
　　　　P_真 := sum_{i: 真のゴール} P_i
　　　　E_偽 := sum_{i: 偽のゴール} E_i
　　　　E_真 := sum_{i: 真のゴール} E_i
とします（当然 P_偽 + P_真 = 1 です）。このとき
　　　　部分ゲームが偽のゴールで終了する場合のターン数の期待値 = E_偽 / P_偽 （P_偽 ≠ 0 の場合）
　　　　部分ゲームが真のゴールで終了する場合のターン数の期待値 = E_真 / P_真
であることに注意してください。

　元々のゲームは「部分ゲームを真のゴールで終了するまで繰り返す」というゲームです。そして、確率 P で成功する試行を成功するまで行う場合の試行回数の期待値は 1 / P です。そのため、部分ゲームが偽のゴールで終了してしまう回数の期待値は 1/P_真 - 1 であるので、元々のゲームでのターン数の期待値は
　　　　(1/P_真 - 1) * (E_偽 / P_偽) + 1 * (E_真 / P_真) = (E_偽 + E_真) / P_真
となります。なおこの式は P_偽 = 0（つまり K = 0）の場合にも成立します。そして P_真 = 0 のケースは最初に除外したので 0 除算は発生しません。


　＊　＊　＊　＊


　この問題は、本質部分だけを残して問題設定をよりシンプルにすると、以下のようになります。

〔問題〕
　i 番目の項目が確率 P_i で当たり、スコアを S_i 点得られるルーレットがあります（sum_i P_i = 1）。そして、いくつか（すべてではない）の項目にはルーレットへの再挑戦権も付いています。挑戦権を１個持っている場合に得られる合計スコアの期待値は？

〔解答〕
　　　　１回のルーレットで得られるスコアの期待値 / １回のルーレットで再挑戦権を得られない確率