AtCoder 修行日記#91 - Flying Cat Penguin

91日目
ABCのC問題に取り組み中。
茶色レベルのD問題も余裕があれば取り組み中。

勉強用のコンテンツはここから。
https://kenkoooo.com/atcoder/#/table/

進捗と一言感想

[C問題] 1問(残り120問)

ABC146: Buy an Integer

最近は問題を解いていると、わかっちゃいるけど単純な解法ではTLEになりすぎて全然太刀打ちができなくなってきている感じです。
今回は二分探索が必要なアルゴリズムでした。今回も公式解説と他の方のコードを見てAC。

【単純に作ると時間切れになるケース】

a, b, x = map(int, input().split())
 
answer = 0
while(True):
  if x < a*(answer+1)+b*int(len(str(answer+1))):
    break
  else:
    answer += 1
 
print(answer)

【二分探索を適用したケース】

a, b, x = map(int, input().split())
 
minNumber, maxNumber = 0, 10**9+1
answer = 0
while(minNumber+1 < maxNumber):
    n = (minNumber+maxNumber)//2
    if a*n + b*len(str(n)) > x:
        maxNumber = n
    else:
        minNumber = n
 
print(minNumber)