競技プログラミングのための精進履歴をブログ形式で残していきます。
目標は AtCoder 水色！
今のレートは茶色です。
本日の精進ツリーは以下のとおり。
精進ツリー
ABC194: D – Journey
ABC194より、 ABC194: D – Journeyを解きました。
難易度は緑色。
提出コードはこちら。
N = int(input())
"""
NOTE:
・何もわからんかったので解説見ました。
https://blog.hamayanhamayan.com/entry/2021/03/07/000733
・「有効なものが来るまでカードを引く期待値は、有効なカードを引く確率の逆数になる。」というのがこの問題のポイントらしい。
https://kmjp.hatenablog.jp/entry/2014/12/22/0900
・「連結グラフ」とは、グラフ上の任意の2頂点間に道が存在するグラフのこと = たどれればいい
・「連結された頂点」と「連結されていない頂点」の集合があるとすると、「連結された頂点」のどこにいても、
連結数を増やすには、「連結されていない頂点の個数」/ N の確率にする必要がある
・ある頂点を引いた時には、その頂点も「連結された頂点」に含まれるので、次に有効な頂点を引ける確率は、(N-1)
/Nになる
= 次に有効な頂点を引ける期待値は、確率の逆数
"""
ans = 0
for i in range(1, N)[::-1]:
ans += N / (N - i)
print(ans)
まとめ
今日の ABC195 で灰パフォ出してしまってレート下がったので心が折れました。
気を取り直して頑張っていきます。
