PythonでABC146-Cを解く

はじめに

二分探索の問題を解きます。

Buy an Integer

売られている全ての整数を試すとTLEになります。ですので、うまく計算量を落さないといけません、そこで二分探索を使います。二分探索は雑に説明すると、両端から範囲を狭めていって目的の解を探す手法です。詳しい解説。
二分探索の計算量は$O(log N)$なので間に合います。

a,b,x = map(int,input().split())

max_n = 10**9+1 #nの最大値が10**9なので+1
min_n = 0
while max_n - min_n > 1:
    mid_n = (max_n+min_n)//2
    if x < a*(mid_n)+b*len(str(mid_n)):
        max_n = mid_n
    else:
        min_n = mid_n
        
print(min_n)

まとめ

二分探索をうまく使えるようになれば、大きく計算量を落せるのでマスターしたい。ではまた。