AtCoder Beginner Contest 126 C - Dice and Coin【Python】

https://atcoder.jp/contests/abc126/tasks/abc126_c

AtCoder ProblemsのRecommendationでDifficulty: 638、Solve Probability: 42%でした。

Kを2で割っていき、サイコロの目がある以上ある値未満の場合のコインを降る回数を求め、確率を計算していきました。

import bisect

N, K = map(int, input().split())
# Kを2で割って小数点を切り上げたもののリスト
# (Kになるまでコインを降る回数ごとにその最小のサイコロの目の値のリスト)
l = []
# Kになるまでコインを降る回数のリスト
t = []
k = K
i = 0
while True:
    l.append(k)
    t.append(i)
    if k == 1:
        break
    k = math.ceil(k/2)
    i += 1
l.reverse()
t.reverse()
ans = 0
for i in range(1, N+1):
    # 二分探索でコインを降る回数を求める
    ans += (1 / N) * (1 / 2) ** t[bisect.bisect_right(l, i)-1]

print(ans)