[Python]二分探索 ABC192D

ABC192D

$X$ が 1 文字のとき、答えは 0 か 1 です。以下、そうでない場合を考えます。
$X_{(n)}$は $n$ の狭義単調増加関数です。したがって、$ \max (\ n\ |\ X_{(n)}\leqq M_{(10)}\ )$ を求めれば良い。ただし、$\max M=10^{18}$なので、二分探索することで時間計算量を $O(L\log M)$ とします。

サンプルコード

x = input()
m = int(input())
d = int(max(x))
if len(x) == 1:
    print(+(int(x) <= m))
else: # 二分探索
    L, R = d, m+1
    while R-L > 1:
        M = (L+R) // 2
        a = 0
        # x_Mを10進数変換する
        for i in x:
            a *= M
            a += int(i)
            if a > m: #途中で越えたら中止
                R = M
                break
        else:
            L = M
    print(L - d)

小生のプログラミング能力は貧弱であることは痛感しているが、この問題文は数学的に不正確な点がある。数学力のある参加者は自分で修正しながら解答しなければならなくなるので、数学力がハンデになることがある。これは良くない事態ではないだろうか。