nashidos’s diary

アルゴリズムとか機械学習とか色々

Pythonで二分探索を実装してみる-ABC146



二分探索

本記事ではPythonを使って二分探索を実装していきます。

二分探索とはソートされたデータを高速に探索することができるアルゴリズムです。

ソートされていないものには使えないので注意してください。

二分探索はその名の通り、データを2つに分けて探索するという操作を繰り返しながら探索する方法です。

では実際に問題を解きながら理解していきましょう。

問題

今回は以下の問題を扱います。
atcoder.jp

問題文

高橋くんは整数を 1つ買いに整数屋さんに行きました。
整数屋さんには 1以上 10^9 以下の整数が売られていて、整数 N を買うためには A×N+B×d(N) 円が必要です。ここで、d(N) は Nの十進表記での桁数です。
高橋くんの所持金が X円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1 つもない場合は 0 を出力してください。

制約

入力は全て整数
1≤A≤10^9
1≤B≤10^9
1≤X≤10^18

実装

まず制約をみてみると所持金Xが1≤X≤10^18と非常に範囲が大きいことがわかります。このように明らかに範囲が広い場合は普通に全探索して解くのはほぼ不可能です。

次に注目してみてもらいたいのが今回求めたい整数Nです。整数Nの範囲は 1≤N≤10^9 です。これをソート済みのデータとして扱うことができることに気づくことができれば使うべきアルゴリズムが二分探索であることに気づくことができます。

それでは早速Pythonで二分探索を実装してみます。

a,b,x = map(int,input().split())

max_n = 10**9+1
min_n = 0
while max_n - min_n > 1:
    mid_n = (max_n+min_n)//2
    if x < a*(mid_n)+b*len(str(mid_n)):
        max_n = mid_n
    else:
        min_n = mid_n
        
print(min_n)

それではコードについて説明していきます。

まず、二分探索を行うためにどこから(最大)どこまで(最小)の範囲を探索するかを定義します。

そして探索範囲が1より小さくなるまで回していきます。

冒頭で二分探索はデータを2つに分けて探索するという操作を繰り返すと述べましたが、どこでデータを2つに分けるのかというとデータの中央で区切ります。それが (max_n+min_n)//2の部分ですね。

データの中央が買うことができなければ、それ以上の整数Nを買うことができないのは明らかなので探索する必要がありません。
そして次はデータの中央が買えなかったのでmax_nにmid_nを代入します。
こうすることで、データの中央(データの2分の1)と最小値の範囲の中央(下位4分の1)が買えるかどうか判定することができます。
これを繰り返すことによって2分の1、4分の1、8分の1、16分の1…と徐々に範囲を絞って探索することができます。

逆にデータの中央が買うことができれば、それ以下の整数Nを買うことができるのは明らかなので探索する必要がありません。
そして次はデータの中央が買うことができたのでmin_nにmid_nを代入します。
こうすることで、データの中央(データの2分の1)と最大値の範囲の中央(上位4分の1)が買えるかどうか判定することができます。

このようにデータの中央で区切ることを繰り返し、最終的に1つの答えを導くことができます。

ちなみに先ほどのコードを提出してみると…

submit-result

わずか実行時間17msで通りました。二分探索ってすごいですねぇ…。

今回はループを利用して二分探索を実装していきましたが、再帰を利用して実装する方法もあります。どちらでも書けるようにしておくといいかと思います。

最後にひとこと

この記事を書くために二分探索について改めて勉強していたのですが、二分探索は英語でBinary search(バイナリサーチ)と言うんですね。二分探索をかっこつけて言いたいときはバイナリサーチと言いたいと思います。

おわり