abc126cのノート

概要

一人でできた。

一応確率の問題だが、必要要素がわかれば実装はそこまで重くないのかもしれない

abc126c

atcoder.jp

計算量に余裕があったので愚直にできる。

10⁵ < 2¹⁷なので二倍し続けるのは最大で17回必要。

書いたコード

辞書型でk以上になるまでの必要回数をそれぞれカウントした。かける乗数ごとに集計している（コインを振る回数すなわちが何乗必要か）

whileループ内でtmpがk以上になるまでかけ続け、行った回数を上記の通り集計した。

また、は順序を入れ替え一番最後にかけている。

今思えば以上は必然的に1なので最悪、処理を半分減らせることに気が付いた。

公式解説pdfを見ると、一つずつ確率を求めていた。計算量は変わらないが辞書型でいったん総量を取るのは蛇足だったかもしれない。

n,k = map(int,input().split())
d = {}
ans = 0

for i in range(18):
    d[i] = 0

for i in range(1,n+1):
    tmp = i
    c = 0
    while(tmp < k):
        c += 1
        tmp *= 2
    else:
        d[c] += 1
else:
    for ind,val in d.items():
        ans += val*(1/2)**ind
    
    print(ans/n)