AtCoder Biginner 192 「D - Base n」を解いてみた

目的

• Atcoderで出場した問題で、解けなかった問題の復習をする
  • pypy7.3.0(python)を利用

問題

• 文字列(X)と、整数(M)が与えられ、文字列Xをn進法で数値変換した際に、M以下になるような種類を数え上げる
  • Xは数値の文字列であり、その中で最も大きい整数d(0~9)とし、n >= d + 1以上の範囲を探索する

atcoder.jp

• 例
  • X=22に含まれる最も大きい数字は2であり、10以下の種類は2種類になる
  • 22を3進法表記とみなして得られる値は8
  • 22を4進法表記とみなして得られる値は10
  • 22を5進法表記とみなして得られる値は12

# input
22
10

# output
2

アプローチ

問題をどのように解いていくかの見立てを立てていく

計算量の見立て

• dを1つづ増やしていく(線形探索)と、非常に時間かかりそう(実際TLEになった)

  • M =< 10¹⁸ であり非常に大きい数であるため、O(n)だと終わらない

• 二分探索(binary search)で探索する

  • nを増加させた際に、文字列Xをn進法で数値変換した値は単調増加する(例参照)ため、二分探索法が利用できる
  • O(log n)で探索が終わるので、制限時間内に終わる

qiita.com

• 今回は、問題条件の実装、二分探索の利用までは気付けたが、時間不足と、二分探索の理解不足でACまで至らず・・・orz
  • 線形探索し、TLEした

必要な機能

• 入力値の取得
• Xのうちの最大値 d を求める機能
• 10進数をn進数に変換する機能
• 数値の範囲を探索する機能
  • 二分探索法で探索する

実装

実装する上で詰まった部分を説明していく

• 自分の回答
  • 実行結果: https://atcoder.jp/contests/abc192/submissions/20457362

from collections import deque


def base10_from(num, base):
    i, s, que = 0, 0, deque(list(str(num)))
    while que:
        s += int(que.pop()) * base ** i
        i += 1
    return s


def binary_search(x, m, d):
    if len(x) == 1:
        if int(x) > m:
            return 0
        else:
            return 1

    low = d
    high = m + 1

    while high - low > 1:
        mid = (low + high) // 2
        guess = base10_from(x, mid)

        if guess > m:
            high = mid
        else:
            low = mid
    return low - d


def main():
    X, M = input(), int(input())
    d = max(list(map(int, list(X))))
    print(binary_search(X, M, d))


if __name__ == '__main__':
    main()

最大値 d を求める機能

• dの取得は、文字列Xをlist化し、それぞれの要素をintに変換した上で、組み込み関数であるmax()を使って、list内の最大値を取得している

def main():
    X, M = input(), int(input())
    d = max(list(map(int, list(X))))


if __name__ == '__main__':
    main()

10進数をn進数に変換する機能

• 数値num, 基数baseを受け取り、それらを下記の考え方の基づき計算する

chugaku-juken.com

• ちなみに、各桁の数値の取得は、文字列をlist化、stackに変換し、桁の小さい方から取得している
  • listのままでも実装可能であるが、pythonでlist型のpopは線形探索(O(n))で低速
  • collections.deque を利用した際には、popはO(1)になる

qiita.com

def base10_from(num, base):
    i, s, que = 0, 0, deque(list(str(num)))
    while que:
        # NOTE: i桁目の数値を計算する
        s += int(que.pop()) * base ** i
        i += 1
    return s

数値の範囲を探索する機能

Xが1桁の場合のみ、特殊な場合になるため注意が必要

• Xが1桁の場合の場合dの値に寄らず、解が決まる
  • X > M の場合は、解なし
  • X <= M の場合は、dの値を変化させても値が変わらないため、1種類のみになる
• Xが2桁以上の場合に、二分探索を実施
  • highは、解が必ずそれ以下になる十分大きな値であれば良い
  • high - low > 1の間は、整数midが存在するため、その間は計算を続ける

def binary_search(x, m, d):
    if len(x) == 1:
        if int(x) > m:
            return 0
        else:
            return 1

    low = d
    high = m + 1

    while high - low > 1:
        mid = (low + high) // 2
        guess = base10_from(x, mid)

        if guess > m:
            high = mid
        else:
            low = mid
    return low - d

学び

• 二分探索早いし、よく使うのでこれを機会に理解できて良かった