Codeforces 8VC Venture Cup 2016 - Elimination Round D. Jerry's Protest

問題を理解するのに苦戦した。

codeforces.com

解法

得点差にのみ着目して DP を行う。

  • dp[i][j] := i 試合目まで行ったとき、得点差が j であるような場合の数

試合数は 2 回で、得点差は 5000 通り、遷移数は 5000 通りなので 2*5000*5000 回程度ループを回せば更新できる。

2 試合目での得点差が j なら3試合目で j+1 点差を付けて勝てばいいことを考えれば、条件を満たすパターン数を求めることができる。

今回求めたいのは確率なので、条件を満たすパターン数を全パターン数で割ればいい。

Codeforces 8VC Venture Cup 2016 - Elimination Roun ...

ゲーム系の問題は問題文がきちんと読めないと解けないので苦手。