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$ という等式が成り立つ。
変形して $pX=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} + \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

以下の記事も参考にしました.

[AtCoder] ABC 194 D – Journey | ヤマカサの競技プログラミング
問題 方針 確率 \( p \) が起こるまでの期待値 確率 \( p \) が起こるまでの期待値を \( E \) とします。\( i \) 回目に初めて確率 \( p \) ...

まとめ

期待値の性質を知っていないとなかなか厳しい問題ですね.勉強になりました.

コメント