Codeforces 8VC Venture Cup 2016 - Elimination Round D. Jerry's Protest
問題を理解するのに苦戦した。
解法
得点差にのみ着目して DP を行う。
- dp[i][j] := i 試合目まで行ったとき、得点差が j であるような場合の数
試合数は 2 回で、得点差は 5000 通り、遷移数は 5000 通りなので 2*5000*5000 回程度ループを回せば更新できる。
2 試合目での得点差が j なら3試合目で j+1 点差を付けて勝てばいいことを考えれば、条件を満たすパターン数を求めることができる。
今回求めたいのは確率なので、条件を満たすパターン数を全パターン数で割ればいい。
Codeforces 8VC Venture Cup 2016 - Elimination Roun ...
ゲーム系の問題は問題文がきちんと読めないと解けないので苦手。