0. はじめに
この記事は、AtCoder ABC192 D問題について、初心者が書く初心者向け解説記事です。言語は、Python3です。
- 公式解説を読んだが。。。わからん。
- 二分探索ってなに？半分にするやつだっけ？
- 二分探索を、この問題でどうやって実装すればいいの？
AtCoder初心者である私は、解説を読んでもこんな感じでした。
まず、二分探索の説明を行い、それを踏まえてD問題の解説を試みます。同じく解けなかったAtCoder初心者の理解の一助になることを目的とします。
二分探索の説明・コードについて、以下の書籍を参考にしました。
参考文献
増井敏克(2020)『Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量』、翔泳社
目次
- 二分探索とは？
- 二分探索 Pythonコード
- ABC192 D問題で、二分探索を思いつくには何が足りなかった？
- ABC192 D問題 Python実装
- まとめ
1. 二分探索とは？
二分探索は、探索範囲を半分ずつに狭めていくことで、目的の値を求める探索アルゴリズムです。具体的に見ていきましょう。
このように、データが昇順に並んだリストがあるとします。このリストから、Value 30のIndexを探します。まず、最も左側のIndexをLeft, 最も右側のIndexをRightとします。次に、このリストの中央のIndexであるMiddleを求めます。Middleは、次の式で求まります。
Middle = (Left + Right) // 2
このリストが昇順に並んでいることはわかっています。さきほど求めた中央のIndex MiddleのValue 40と求めたいValue 30を比較すると、MiddleのValue 40の方が大きいです。となると、Middleより右側にValue 30がないことは明らかです。よって、右側の探索範囲をMiddleまで、絞り込むことができます。
これを繰り返し行うと、最終的にはValue 30とMiddleのValueが一致し、Value 30のIndexが3であることがわかります。
このように二分探索では、探索範囲を半分半分と絞り込んでいくため、線形探索と比べて高速に処理することができます。リストにふくまれるデータが２倍になったとき、線形探索では処理量が２倍になりますが、二分探索では１回処理量が増えるだけです。ただ二分探索を適用する条件として、データは昇順か降順に並んでいる必要があります。
2. 二分探索 Pythonコード
data = [0, 10, 20, 30, 40, 50, 60, 70, 80]
Value = 30
Left = 0
Right = 8
while Left <= Right:
# 中央のIndex Middleの算出します。
Middle = (Left + Right) // 2
# 探索しているValueとMiddelのValueを比較し、探索範囲を絞り込みます。
if Value == data[Middle]:
print(Middle)
break
elif Value > data[Middle]:
Left = Middle
elif Value < data[Middle]:
Right = Middle
3. ABC192 D問題で、二分探索を思いつくには何が足りなかった？
コンテスト時、そもそも二分探索へ考えが至りませんでした。問題文やAtCoder公式・ユーザー解説から、どのように問題を読み解けば二分探索に気づけたのか振り返ります。
1. 問題文の制約 1 ≤ M ≤ 1018
AtCoderのジャッジでは1秒あたり108回程度の計算が可能と言われています。今回の問題で、Mは最大で1018 となります。nをひとつずつ増やしながら線形探索で実装すると、最大で1018オーダー程度の判定を行わないといけなくなります。それでは、TLEになるので線形探索ではダメなことがわかります。
C++入門 AtCoder Programming Guide for beginners (APG4b) EX21 - 計算量の見積もり
D - Base n 解説 by hamayanhamayanさん
2. 単調増加
kyopro_friendsさんの解説に、狭義単調増加という言葉が出てきました。
Xをn進法表記とみなしたときの値をf(n)とすると、fは狭義単調増加です。したがって、f(n)≤Mを満たすような最大のnを二分探索により求めることができ、問題が解けました。
D - Base n 解説 by kyopro_friendsさん
狭義単調増加：x1 < x2 ならば f(x1) < f(x2)を満たすときf(x)は(その区間内で)狭義単調増加と言います。xが増えれば、yも増えるような関数です。
問題文で具体的に見ていきましょう。
問題 入力例１にて、 X = 22なので、d = 2です。
"d+1以上の整数nを選んでXをn進法表記の数とみなして得られる値" とありますので、nは3から始まります。
nが増えるにつれて、f(n)が増えていることがわかります。
この並び。。。昇順になっていますね。二分探索適用の条件を満たしてそうです！
二分探索が説明されるさいに、"データの並びは昇順か降順になっている必要がある"と説明があります。この表現と、単調増加や単調減少という表現が、二分探索の適用を考える上で同じ意味でとらえる必要がありました。
自分が二分探索へ考えがいたらなかった原因としては、
計算量を考えていなかった。
狭義単調増加が、二分探索適用の可能性を示していることをわかってなかった。
少なくともこの２つがありました。
4. ABC192 D問題 Python実装
D問題を解く上で、二分探索が必要なことはわかったので実装していきたいと思います。実装のイメージをつけるうえで、maple116さんの解説も参考にさせていただきました。
実装は、下記のイメージです。 （入力例１にて、 X = 22, M = 10の場合）
1. 標準入力
まず、X, Mを受け取り、dを求めます。dは、Xに含まれる最も大きな数字です。
Xをリストで受け取り、dを組み込み関数max()で求めます。
X = list(map(int,input()))
M = int(input())
d = max(X)
2. Xをn進法表記の数とみなして値を返す関数
関数をつくります。
def n_function(n, X):
f = 0
for i in range(len(X)):
f = f + X[-(i + 1)] * n ** i
return f
3. 二分探索の実装
二分探索を実装していきます。
Xが一桁の時は、答えは0か1です。Xが一桁の時のf(n)を書くと、こうなります。
f(n) = X * n0 = X
一桁の時は、何進数でもf(n)は１種類しか返しません。その値が、M以上なら１種類。M以下なら0種類です。
Xが二桁以上のことを考えます。
入力例１にて、 X = 22, M = 10の場合
Left、Rightを設定します。Leftは、nがd + 1以上なので、Leftをdに設定しておけば探索範囲をカバーできそうです。Rightですが、f(n)<=1018です。nは、f(n)より大きくなることはなさそうなので、Rightを<=1018+1に設定しておけば良さそうです。
次に、引数dの時に、関数が返す値がMより大きいかったら答えは、0です。あとは、Middleの設定、Mとの比較、Left, Rightの置き直しを実装します。
絞り込みを続けた終盤を考えましょう。Left, Rightが隣り合うところまで絞り込まれました。整数nは、d + 1以上です。d + 1以上でM以下を満たしてるのは、赤丸の8, 10の2種類です。Left - d = 4 - 2 = 2種類となります。
以下、コードです。
# 標準入力
X = list(map(int,input()))
M = int(input())
d = max(X)
# Xをn進法表記の数とみなして値を返す関数
def n_function(n, X):
f = 0
for i in range(len(X)):
f = f + X[-(i + 1)] * n ** i
return f
# 二分探索実装
# Xが１桁かどうかの判定
if len(X) != 1:
# Left, Rightの設定
Left, Right = d, 10 ** 18 + 1
# 引数dの戻り値がMより大きいなら、得られる値はないので0を出力
if n_function(d, X) > M:
print(0)
else:
while Right - Left > 1:
Middle = (Left + Right) // 2
Value = n_function(Middle, X)
if Value <= M:
Left = Middle
else:
Right = Middle
print(Left - d)
else:
if X[0] <= M:
print(1)
else:
print(0)
5. まとめ
今回の記事では、二分探索の説明を踏まえ、ABC 192Dでの二分探索の実装の説明を試みました。二分探索が必要か考えるさいには、
- AtCoderで処理できる計算量とアルゴリズムの計算量を理解できるようになる。
- 二分探索を適用できるかは、昇順・降順の関係がないか見る。考える。
こういった点は、最低限必要となるかと思います。