ダブリング→二分探索

ダブリングした結果に対して二分探索する時、別個の部品と考えるより密結合にした方がコードもシンプルだし速い

python

# find x s.t. f(x) = y
x = 0
for i in range(30 - 1, -1, -1):
    dy = fs[i]
    if y >= dy:
        y -= dy
        x += 2 ** i

PAST2M python

for i in range(30 - 1, -1, -1):
    up = db_ups[i][cur % D]
    if countdown >= up:
        countdown -= up
        cur = db_next[i][cur % D]
        ret += 2 ** i

関連

• 最小共通祖先のダブリングによる実装ではダブリング結果に対する二分探索をする
  • AOJでベリファイした時、この二分探索のやり方でないとTLEだった