ABC194_D – Journey

問題

2度ほど解けず、解説を確認後3度目の挑戦。

成功確率pの事象が成功するまでの期待値$e$は、期待値の定義から、確率回数となるので、以下のような式になる。
$$ e = p1 + (1-p) * (e+1)$$
1回で成功する確率がp、それ以外の確率で(e+1)回の回数となる。
この式からeを求めると、$e=\frac{1}{p}$となる。

今回の問題では、成功確率は以下のようになる。
$1回目 : \frac{N-1}{N}$
$2回目 : \frac{N-2}{N}$
$i回目 : \frac{N-i}{N}$
$N-1回目 : \frac{1}{N}$

期待値は成功確率の逆数なので、以下のようになる。
$1回目 : \frac{N}{N-1}$
$2回目 : \frac{N}{N-2}$
$i回目 : \frac{N}{N-i}$
$N-1回目 : \frac{N}{1}$

$1$回目から$N-1$回目までの和が全体の回数となるので、答えは以下のようになる。
$$ans = \frac{N}{N-1} + \frac{N}{N-2} + … + \frac{N}{1}$$