ebisuke競プロ初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。C言語も少しだけ勉強中

AtCoder-ABC194 D - Journey【Python解答例】

f:id:ebisuke33:20210317145916p:plain
AtCoder Beginner Contest194のD - JourneyについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 194 - AtCoder


AtCoder Beginner Contest194 D - Journey

D - Journey

問題文

頂点
1 から頂点 N までの N 頂点からなるグラフの頂点 1 に高橋君がいます。今このグラフに辺は 1 つも張られていません。
高橋君は以下の操作を繰り返します。
操作 :
(今高橋君がいる頂点も含めた) N 個の頂点の中から 1 つランダムに選ぶ。各頂点が選ばれる確率は全て 1/N であり、選択は操作毎に独立である。
今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。
グラフが連結になるまでに行われる操作の回数の期待値を求めてください。

制約

・2≤N≤10^5

解答例

n = int(input())

res = 0
for i in range(1,n):
    res += n / (n - i)

print(res)

解説

N個の頂点があり、すべての頂点にたどり着くまでの操作回数の期待値を答える問題です。

解説であげられている「確率 p(p≠0) で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は 1/p である」という重要な事実を知らず迷走していました (^_^;)

解説の通りに計算するとあっさりACでした…



コンプガチャの期待値とかで検索すると答えに近い大ヒントがごろごろでてきました。
初めてD問題を解くチャンスでしたが逃してしまいましたね (^_^;)


ABC194の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com