Codeforces ラウンド #105 (ディビジョン 2) D 概率DP_html/css_WEB-ITnose

質問

長い間考えた結果、質問の意味が少し曖昧になりました。 A と B は順番に描画します。最初に白を引いた人が勝ちます。最後に白が引けなかった場合、B が引いた後は、さらに 1 つのアイテムが失われます。

境界としてのターゲット状態にまだ基づいており、現在の状態からターゲット状態までに必要な確率は次の方程式です

dp[i][j] は、A の現在の描画番であるときに、i の白が存在する確率を表します。 J 黒 A が勝ちます

その後、現在 4 つの可能な転送があります

1: A が白を引くと、直接勝ち、続行する必要がないため、他の状態方程式との関係はありません

2: A黒を引き、次に B が白を引きます。その後、A が負けます。以下で必要な答えには影響しません。したがって、この答えには関係ありません

3: A が黒を引き、次に B が黒を引き、負けたものが白、つまり dp[i - 1][j - 2] になったとき、これは絶対的な勝ち負けの状態を生成しないため、次のデータの転送と再帰に役立ちます。次の方程式なので、接触する必要があります

4: A が黒を引き、次に B が黒を引き、黒で負けます。これは dp[i][j - 3] です。これは絶対的な勝ち負けを生み出しません。まだ連絡する必要があります

すると、境界 dp[0][0] = 0 になります。なぜなら、A の番になると、描画するものは何も残っていないためです。つまり、この時点ですべてが描画されているということになります。質問の条件に従って B が勝ちます

また、dp[i][0] が A が引く番になったとき、黒いものはもう引かれていません。その場合、A は白いものしか引くことができません。 win

はdp [0] [j]がaのターンである場合、白いものがないので、彼は負けなければなりません。