🐶

ABC180 D - Takahashi Unevolvedを二分探索で解く

2022/02/01に公開

Python

D - Takahashi Unevolved

公式解説はスマートな実装でした。
ただ私はあまり考察が不得手なので、二分探索で解きました。
あまり考察量は変わらなかったかもしれませんが。。。

めぐる式二分探索を用います。

$X \times A$ を繰り返す数列を考えて実験すると、その公差は $X \times A^{n} \times (A - 1)$ であり、これは単調増加であることがわかります。

X = 2, A = 3のとき
6 -> 18 -> 54 -> 162
公差: 12 -> 36 -> 108 (単調増加)

$X \times A^{n} \times (A - 1)$ については、公差が $X \times A^{n+1} - X \times A^{n}$ で求まり、これをまとめると $X \times A^{n} \times (A-1)$ となることから導くことができます。

あとは二分探索で $X \times A$ の増加量が $B$ を超えないの値を求めます。
is_ok関数は「 $X \times A$ の増加量が $B$ を超えない」という判定を行います。

ngには、べき乗計算なので100もあれば十分にBよりも大きいと考えてよいと判断します。

まだ経験値を得る余裕がある場合は、 $B$ をギリギリまで足して帳尻を合わせます。
Y未満である必要があるので、(Y-X)//Bではなく、(Y-X-1)//bであることに注意します。

d-meguru.py

X, Y, A, B = list(map(int, input().split()))

# コーナーケース対策
if A >= Y and B >= Y:
    print(0)
    exit()

def is_ok(n):
    return (X * (A ** n)) * (A - 1) < B

def meguru_bisect(ng, ok):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

ng = 100
ok = -1

ans = 0

xa = X * A
xb = X + B
if xa < xb:
    num = meguru_bisect(ng, ok)
    ans += num
    X = xa ** num

ans += (Y - X - 1) // B

print(ans)

D - Takahashi Unevolved

Discussion