ABC194のD問題を解く

解けなかったABC194のD問題を理解しつつ、解いていきます。
解説動画を見て目から鱗が落ちました。

N個の頂点があって、高橋くんは頂点1にいて、自分自身がいる頂点も含めてランダムに頂点を選びながら頂点どうしを線で結んでいくときに、全ての頂点を連結できる操作回数の期待値を求める問題です。

atcoder.jp


問題文は理解できたのですが、最初の5分くらいは入力例と出力例を読んでもよく理解できませんでした。
実際に手を動かして計算して本当の意味で問題を理解できたのですが、解き方の検討がつかず、諦めました。

一番大事なポイントは
「有効なのが来るまでカードを引く期待値は、有効なカードを引く確率の逆数」
ということです。

他の方の解説を読むと、これは競プロで生きていくには知識として持っておいた方が良いことらしいです。。。

どうしてそうなるかは、動画の解説がとてもわかりやすかったので、その理由を説明している位置からの動画を貼っておきます。
期待値は \sum_{i=0}^{\infty}i(1-p)^{i-1}pなんて考えて行き詰まっていた私は目から鱗が落ちる解説でした。

youtu.be

上のポイントがわかると、あとはそれほど難しくなくて、
N個のうちまだ選んでない頂点を引き当てる確率を計算して、期待値なのでその逆数を全部の頂点を選ぶまで足していきます。

N = int(input())
ans = 0
for i in range(1, N):
    ans += N / i
print(ans)

公式解説の動画の説明は、期待値を視覚的に表現していて、本当に新鮮でした。