AtCoder Beginner Contest 194: D – Journeyの初心者解説（期待値の性質）

期待値関連の問題ですね．期待値の性質で今回はじめて知ったものがあったので紹介します．

問題

公式問題はコチラ．

問題文

$N$ 個の頂点があるグラフあり，高橋くんは今頂点 $1$ にいて現在グラフに線は張られていません．以下の操作を行うとき，グラフが連結となるまでの操作回数の期待値を求めてください．

操作： $N$ 個の頂点のうち1つを選んで無向辺を張り，選んだ頂点に移動する．

ただし，頂点を選ぶ確率はすべて $\frac{1}{N}$ とする．

制約

$2 \leq N \leq 10^{5}$

解説

考え方

公式解説はコチラ．

結構重要なことですが，以下の事実があるようです．これ知らないと解けませんね ^^;;

確率 $p (p \neq 0)$ で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は $\frac{1}{p}$ である。
証明：
求める期待値を $X$ とする。1 回試行して、成功したらそこで終わり、失敗したら全く同じ状況でやり直しなので $X = 1 + (1 - p) X$ という等式が成り立つ。
変形して $p X = 1$ なので $X = \frac{1}{p}$ である。
https://atcoder.jp/contests/abc194/editorial/823

上記の証明が私にはあまりしっくり来なかったのですが，別のサイトの以下の文面でしっくりきました．失敗したときは 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} + \dots + \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;
}