期待値関連の問題ですね．期待値の性質で今回はじめて知ったものがあったので紹介します．
問題
公式問題はコチラ．
問題文
$N$ 個の頂点があるグラフあり，高橋くんは今頂点 $1$ にいて現在グラフに線は張られていません．以下の操作を行うとき，グラフが連結となるまでの操作回数の期待値を求めてください．
操作：$N$ 個の頂点のうち1つを選んで無向辺を張り，選んだ頂点に移動する．
ただし，頂点を選ぶ確率はすべて $\frac{1}{N}$ とする．
制約
- $2 \leq N \leq 10^5$
解説
考え方
公式解説はコチラ．
結構重要なことですが，以下の事実があるようです．これ知らないと解けませんね ^^;;
確率 $p (p \neq 0)$ で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は $\frac{1}{p}$ である。
証明：
https://atcoder.jp/contests/abc194/editorial/823
求める期待値を $X$ とする。1 回試行して、成功したらそこで終わり、失敗したら全く同じ状況でやり直しなので $X=1+(1−p)X$ という等式が成り立つ。
変形して $pX=1$ なので $X=\frac{1}{p}$ である。
上記の証明が私にはあまりしっくり来なかったのですが，別のサイトの以下の文面でしっくりきました．失敗したときは 1 回試行が追加されるので期待値が $E + 1$ になるということを考えると，下記の式で納得です！
なお，期待値の意味を考えて $E=p+(1−p)(E+1)$ という漸化式を立てて一発で導出することもできる。
https://manabitimes.jp/math/1094
たとえば，$N = 2$ のとき頂点 $1$ から頂点 $2$ を選択する確率は $\frac{1}{2}$ で，これを成功するまで行うときの期待値は $2$ ということになります．例題の答えと合致しますね．
また，頂点が 3 つのときを考えると，「頂点 $1$ から頂点 $2$ or 頂点 $3$ に移動する確率」は $\frac{2}{3}$ で「移動した先の頂点から残りの頂点まで移動する確率」は $\frac{1}{3}$ となります．すなわち，期待値の合計は $1.5 + 3 = 4.5$ となり，例題と合致します．
ここで，すでに連結した頂点の集合を $S$ として $S$ の要素数を $|S|$ とすると，連結していない頂点に到達する確率は $\frac{N-|S|}{N}$ となります．よって，連結していない頂点に到達する期待値は先の事実から $\frac{N}{N-|S|}$ となります．$|S| = 1$ から $|S| = N$ になるまでの期待値を求めればよく，これは以下のような式で表されます．
$$ \frac{N}{N-1} + \frac{N}{N-2} + \cdots + \frac{N}{1}$$
これは $O(N)$ の計算で簡単に求めることができます．
ソースコード
#include <bits/stdc++.h>
#include <math.h>
#include <string>
using namespace std;
int main(void) {
int N;
cin >> N;
double ans = 0;
for (int i=1; i<N; i++) {
ans += (double)N / i;
}
printf("%0.10f\n", ans);
return 0;
}はじめ cout で表示していたのですが，WA となってしまったので printf で %0.10f をつけてみたら AC しました．以下の指定がある場合は小数点 6 桁までの表示は必要そうですね．
想定解答との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われる。
https://atcoder.jp/contests/abc194/tasks/abc194_d
以下の記事も参考にしました．
まとめ
期待値の性質を知っていないとなかなか厳しい問題ですね．勉強になりました．
コメント