基数変換

ABC192 Base n

この問題をやっていて思いのほか詰まったので忘れないうちに整理しておく。

Pythonでの基数変換

基本的には、文字列をintにキャストする際に第2引数に突っ込めばその基数で解釈してくれる。

base_10 = '9999'
base_16 = int(base_10, 16)
print(base_16) #=> 39321
print(hex(base_16)) #=> 0x123456
print(int('F', 16)) #=> 15

ただし、第2引数に指定できるのは36まで（[0-9] + [a-z] で36文字しかないから）。

[0-9]のみからなる文字列Xをn進数で解釈したい

今回の問題は余裕で基数に36を超えた数が入るので、自分で実装する必要がある。

ここで、問題文からxは^[1-9]\d*$を満たす文字列であり、これをn進数で解釈するとしよう。 問題の制約上、想定すべきnはxの最大digitをdとしたときにn > dの範囲のみとなる。

base_n = 0
for c in x:
    base_n = base_n * n + int(c)

わかりやすいように、まず2進数の例を考える。

ここに2進数1100100がある。これを先頭から見て10進数に直す。

base_n = 1     # 先頭の数字
base_n = 10    # base_n <<= 1、つまりbase_n *= n
base_n = 11    # xに一致させる、つまりbase_n += int(c)

このように2進数で考えると、先ほどのコードは次の桁があればシフトして、ビットが立っていれば足すという操作に該当する。

次に、後ろ側から処理することも考えておく。これもやっていることは本質的には同じ。

base_n = 0
k = 1
for c in x[::-1]:
    base_n += int(c)*k
    k *= n

あとは、xをn進数で解釈した際の値を$f(n)$とおけば、$f(n)$は単調増加なので二分探索が可能であることを利用すればよい。

コーナーケースの検証

ただし、$|x|=1$はコーナーケースを考える必要がある。

$|x|>1$の場合、2桁目のdigitが存在する時点で、$f(n)\ge n$を満たすことは明らかであり、二分探索のng側をm+1とおけばそれで済む。

しかし、$|x|=1$の場合はいくらnを大きくしようが、その値はdである。

つまり、1桁のケースだけ場合分けをして、$d\le m$かを検証すればよい。

これは、最初にif len(x)==1:としてもよいし、$d\le m$かつ$|x|=1$の場合に二分探索がngの初期値より1小さい値となることを利用して場合分けしてもよい。

具体的には下記の実装において、

x = input()
m = int(input())
d = max(int(c) for c in x)

def is_ok(k):
    n = 0
    for c in x: n = n*k + int(c)
    return 1 if n<=m else 0

ok = d
ng = INF = 1<<60
while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if is_ok(mid):
        ok=mid
    else:
        ng=mid

最後の出力は下記のいずれでもよい。

print(ok-d if ok!=INF-1 else 1)

または、

if len(x)==1:
    print(1 if d<=m else 0)
else:
    print(ok-d)