D - Journey Editorial by QCFium
重要な事実として以下があります。
確率 \(p(p \neq 0)\) で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は \(\frac{1}{p}\) である。
証明 :
求める期待値を \(X\) とする。\(1\) 回試行して、成功したらそこで終わり、失敗したら全く同じ状況でやり直しなので \(X = 1 + (1 - p) X\) という等式が成り立つ。
変形して \(pX = 1\) なので \(X = \frac{1}{p}\) である。
今回の問題で、「今高橋君がいる連結成分に含まれる頂点集合」を \(S\) と表すことにします。また、\(S\) の要素数を \(|S|\) と表します。
操作において \(S\) に含まれない頂点が選ばれた場合、そしてその場合に限り \(|S|\) が \(1\) 大きくなります。
\(S\) に含まれない頂点が初めて選ばれるまでに必要な操作回数の期待値は冒頭の事実より \(\frac{1}{\frac{N - |S|}{N}} = \frac{N}{N - |S|}\) であり、\(|S| = 1\) の状態から始めて \(|S| = N\) になった時に終了なので、答えは \(\frac{N}{N - 1} + \frac{N}{N - 2} + \frac{N}{N - 3} + \dots + \frac{N}{1}\) です。
これは \(O(N)\) で計算できるので解けました。
答えの値は最大で \(1.2 \times 10^6\) 程度なので、少なくとも倍精度浮動小数点数 (double型)を使えば誤差も問題になりません。
posted:
last update: