フワッティーの挑戦日記

深層学習、Atcoderなどの勉強の軌跡を綴っていきます

AtCoder Beginner Contest(ABC) 194 D - Journey の解説

はじめに

この間のAtCoder Beginner Contest(ABC)194のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。

D - Journeyの問題文

頂点 $1$ から頂点 $N$ までの $N$ 頂点からなるグラフの頂点 $1$ に高橋君がいます。今このグラフに辺は $1$ つも張られていません。高橋君は以下の操作を繰り返します。

操作 :

(今高橋君がいる頂点も含めた) $N$ 個の頂点の中から $1$ つランダムに選ぶ。各頂点が選ばれる確率は全て $\frac{1}{N}$ であり、選択は操作毎に独立である。
今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。

グラフが連結になるまでに行われる操作の回数の期待値を求めてください。

ただし、 $2 \leq N \leq 10^ 5$ である。

解答までの道のり

問題文をよく見る

まず問題文を見て思うのが、「グラフが連結ってどういう意味？」ということです。（無知）どうやらグラフが連結というのは「任意の重複しない2頂点を選択したときに、それらを結ぶパスが存在すること」です。つまり、図のようなことを言っています。

f:id:fwatty:20210307102353p:plain — 連結と非連結

この図を見るにどうやら今回の問題ではグラフが連結になるということはすべての頂点を1回以上選択するというのに言い換えられるということがわかります。少しとっつきやすくなったかな・・・？

実験してみる

なんか $N=2$ ではあまり参考にならなさそうなので $N=3$ で考えます。

・・・わからない！ AtCoderの公式の解説を見ても、これはどうやら知っているかどうかが決め手となる問題みたいです。

必要となる知識

これは公式解説に詳しいことが載っているのですが、

「確率 $p (p \neq 0)$ で成功する試行を、成功するまで行うときの試行回数の期待値は $\frac{1}{p}$ である。」

というものです。

知識を持った上で実験

$N=3$ で考えます。 $N=3$ で、すべての頂点を1回以上選択するルートは $1 \rightarrow 2 \rightarrow 3$ 、 $1 \rightarrow 3 \rightarrow 2$ があります。 今回は問題の性質上、頂点 $1$ 以外の区別はしなくても良いので、 $1 \rightarrow 2\mbox{か}3 \rightarrow \mbox{余り}$ という感じになります。

まず、 $1 \rightarrow 2\mbox{か}3$ のとき、このように遷移する確率は $\frac{2}{3}$ なので、期待値は $\frac{3}{2}$ となります。

次に、 $2\mbox{か}3 \rightarrow \mbox{余り}$ のとき、このように遷移する確率は $\frac{1}{3}$ なので、期待値は $3$ となります。

これらを足し合わせると $\frac{3}{2} + 3 = 4.5$ となります。

解答はこれを $N$ に拡張するだけですね。

解答

N = int(input())

ans = 0
for i in range(1, N):
    ans += N/(N-i)

print(ans)

感想

こんな短い解答なのか・・・。まあ知らなきゃ解けない問題なのでクヨクヨせずに次は頑張ろう！