🐶

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

2022/01/31に公開約1,300字

D - Takahashi Unevolved

https://atcoder.jp/contests/abc180/tasks/abc180_d

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

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

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)

Discussion

ログインするとコメントできます