CodeForces #8VCVentureCup : D. Jerry's Protest

問題

ツボの中に重複のない番号の書かれたボールがn個入っている。
Andrewと Jerryはこのツボの中から同時にボールを一つだけ無作為に選びとり、
番号の大きい方が勝者となる。(選んだボールはツボにまた戻す)

このゲームを3回連続で行った時、
最初の2回は Andrewが勝ち最後の1回は Jerryが勝ったとする。
3回のゲームを通して Jerryの出た番号の和が Andrewより大きくなる確率を求めよ。

解法

d、cを以下のように定義し
勝者が敗者にi枚差・i枚以上差をつけて勝つパターン数を事前に求める。
cはdの累積和から得ることができる。

d[i] := 1回の勝負で勝者が敗者にi枚差をつけて勝つパターン数
c[i] := 1回の勝負で勝者が敗者にi枚以上差をつけて勝つパターン数

d,cより以下の場合の数を、差の最大値(5000)の2重ループで求める。
1戦目. Andrewがi枚差をつけてJerryに勝った
2戦目. Andrewがj枚差をつけてJerryに勝った
3戦目. Jerryがi+j+1枚以上差をつけてAndrewに勝った
d[i] * d[j] * c[i+j+1]