No.475

writer 以外の点数は降順に並べておく. また, 順位によって取得できる得点も計算しておく.

$i$ 番目の人が $r_i$ 位以下ならば writer の点数を上回れないかを二分探索で求める.

$i$ 番目の人まで見たときに, $1 \dots i$ 番の人のいずれもが writer の点数を上回っていない確率を $p(i)$ とする. $i$ 番目より前の人は必ず $r_i$ 位以下であるので, $i$ 番目の人が選べる順位は $N-i$ 個の中の $N-r_i-i$ 個であり,

$$p(i) = p(i-1) \frac{N-r_i-i}{N-i}$$

となる.