【二分木探索】ABC146 Buy an Integer【茶】

AtCoder Python

ABC146 C問題

atcoder.jp

  • 難易度：茶色
  • 時間：30分（1WAが解決できず断念）

最初に書いたコード

桁数を10〜1へ移動させながら最大となるNを探していくアルゴリズムで勝負をかけました。
Nの桁数とiが一致すればそのNを出力するという理屈。
ただnum > 10**9 の場合や最大Nが見つからない場合は例外処理。

import sys
A,B,X=map(int,input().split())
for i in range(10,-1,-1):
  num=(X-B*i)//A
  #print(num)
  if i==10 and num>=10**9:
    print(10**9)
    sys.exit()
  if len(str(num))==i and num>0: 
    print(num)
    sys.exit()
  if i==0: print(0)

WAが1つだけ出ます。しばらく考えて埒が明かない（30分考えて無理ならギブ）。

解説

blog.hamayanhamayan.com

C++で書かれているコードをPythonに変換。
二分木探索で特定のNを両端から探しあてるアルゴリズム。
この場合だと例外処理は必要ない。
どちらにせよ0 も10**9の境界値を経由するアルゴリズムなので「なるほどなー」と感じました。

二分木探索は計算量もO(log(N))で有効活用できそうなので頭に入れておこう。

import sys
A,B,X=map(int,input().split())
ok,ng=0,1000000001

def check(n):
  dx = len(str(n))
  return A*n+B*dx
 
while(ok+1!=ng):
  num=(ok+ng)//2
  if(check(num)<=X): ok=num
  else: ng=num
print(ok)