1. 目的
初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。
本記事は「018 - 023 二分探索」です。
2. 総括
pythonにはbisectがあるのでそれを使えば二分探索はできますが、応用問題に対応するためには自分で書けるように練習する必要があると思いました。
3. 本編
018 - 023 二分探索
018. LDS_4_B - 二分探索
回答
def find_num_by_binary(target_list, num):
# numがtarget_listに含まれているか否かを返す
# target_listは昇順であることが前提
bottom = 0
top = len(target_list) - 1
while top - bottom > 1:
middle = (top + bottom) // 2
if num == target_list[middle]:
return True
if num > target_list[middle]:
bottom = middle
else:
top = middle
if target_list[bottom] == num or target_list[top] == num:
return True
else:
return False
if __name__ == "__main__":
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
count = 0
for t in T:
count += find_num_by_binary(S, t)
print(count)
基礎問題のため自分で書きました。
二分探索の方針は
- まずはターゲットとなるリストを昇順に並べる
- 一番小さい数字を
bottom、一番大きい数字をtopとする - とりあえず、中央らへん(2で割って切り捨てているので正確な中央ではない)を
middleとして、目的となる数値と一致しているか否かを判定する - 判定して一致していない場合、
middleの位置が、bottom側にあるかそれともtop側にあるかをチェック -
bottom側にある場合はtopの値をmiddleの値に置き換え、逆にtop側にある場合はbottomの値をmiddleの値に置き換える - これを永遠と繰り返し、
bottomとtopの差がなくなったら終わり - 最後に
bottomとtopを念のため調べて、returnを返す(念のためなので調べなくてもよいかも？)
です。
019. JOI 2009 本選 2 - ピザ
回答
import bisect
d = int(input()) # 環状1周の長さ
n = int(input()) # 店の数
m = int(input()) # 注文の数
Stores = [0] + [int(input()) for _ in range(n-1)] # 店舗の位置。0番目は本店。
Stores.sort()
Deliveries = [int(input()) for _ in range(m)] # 宅配先
total_distance = 0
for delivery in Deliveries:
left_index = bisect.bisect_left(Stores, delivery)
if left_index >= len(Stores):
distance = min(abs(d - delivery), abs(delivery - Stores[left_index-1]))
else:
distance = min(abs(Stores[left_index] - delivery), abs(delivery - Stores[left_index-1]))
total_distance += distance
print(total_distance)
店の配列をについて各配達先を二分探索します。
方針は、
- 各配達先（
delivery）について配列Storesのどの位置に挿入できるかbisect_leftで探します - 返ってきた
left_indexをもとにdistanceを求めます - 留意すべきは、
left_indexがlen(Stores)以上になる際です。この時は一周回って本店も候補店舗になります - すべての
deliveryについてのdistanceを足しあげたものが答え
です。
distance を計算する際の引き算の個所は、考えるのがめんどくさいのですべてabs()を使って絶対値にしています。
正確にleft_index を判定してやれば、絶対値にする必要ないと思われます。
020. AtCoder Beginner Contest 077 C - Snuke Festival
回答
import bisect
import itertools
N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい
# Cは並び替え不要
A.sort()
B.sort()
# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
b_count = bisect.bisect_left(A, B[i])
b_counts[i] = b_count
cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts
# Cの各要素でBを二分探索。上記で保有しておいたb_countsを活用する
total = 0
for c in C:
count = bisect.bisect_left(B, c)
total += cumsum_b_counts[count]
print(total)
制約にリスト長さが10**5とありますので、forループは1回しか回せそうにないですが、まずは制約を無視して方針を立てます。
方針は、
-
Cの要素でBを二分探索して、リストBのインデックスを取得 - このインデックスまでの
Bの要素でさらにAを二分探索してインデックスを取得 - このインデックスの合計が答え
です。
上記の方針をコードに落とすと下記となります。
# これはTLE
import bisect
N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい
# Cは並び替え不要
A.sort()
B.sort()
total = 0
for c in C:
b_count = bisect.bisect_left(B, c) # bの数量
for b in B[:b_count]:
a_count = bisect.bisect_left(A, b) # aの数量
total += a_count
print(total)
このコードだと、サンプルは通りますが、Nが大きくなると時間がTLEとなり間に合いません。
なのでここからforループを1つ減らす方法を考えます。
「重複して数え上げているものはないか」と考えると、
for b in B[:b_count]:
a_count = bisect.bisect_left(A, b)
ここで何度も同じものを数えていることがわかります。
なのでここで数えている数値を事前に計算して保有しておき、それを使うような方法を考えます。
解決策として僕が現時点で持っている武器はDPと累積和くらいですのでそのどちらかを使うことを考えると、今回は累積和で上手くいきそうです。
# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
b_count = bisect.bisect_left(A, B[i])
b_counts[i] = b_count
cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts
このように一回二分探索した値を累積和として保有しておけば、毎回計算しなおさなくてよくなり計算量を減らすことができました。
021. AtCoder Beginner Contest 023 D - 射撃王
回答
def is_OK(middle_score, H, S, N):
remain_times = []
for i in range(N):
remain_time = (middle_score - H[i]) / S[i]
remain_times.append(remain_time)
remain_times.sort()
for time, remain_time in enumerate(remain_times):
if remain_time < time:
return False
return True
if __name__ == "__main__":
N = int(input())
H = []
S = []
for _ in range(N):
h, s = map(int, input().split())
H.append(h)
S.append(s)
# 取りうるペナルティは初期値Hの最小値～N秒後のHの最大値
# この範囲の中でちょうどよい高さを探しに行く
# 下限と上限を取得
min_score = min(H)
max_score = 0
for i in range(N):
max_score = max(max_score, H[i] * S[i] * N)
# 二分探索実施
while max_score - min_score > 1:
middle_score = (max_score + min_score) // 2
if is_OK(middle_score, H, S, N):
max_score = middle_score
else:
min_score = middle_score
print(max_score)
個人的にはこの形式の二分探索はやや苦手です。
計算量を考えずに解くとすれば、とりあえずすべての風船について0秒後からN秒後までの高さをすべて求めて、行が風船、列が秒とするN × N行列を作成し、最大値をできるだけ小さくするように割っていくことを考えればよさそうです。
しかし、Nの制約が10**5なので2次元配列は作成できません。
なので、2次元配列ではなく1次元で解くことを考えます。
「最大値をできるだけ小さくするように割る」ことを考えるのではなく、「すべての風船を時間内にちょうど割ることができるような高さ」を探すことを考えます。
この考え方の変換が難しいです。
ここができれば、2分探索で下記の方針の通り解きます
- 高さを探すのでとりうる
min_scoreとmax_scoreを算出しておく - 上記二つの間でちょうどよいとこを
middle_scoreで探しに行く - 判定は関数
is_OK(middle_score, H, S, N)で行う - この関数は、すべての風船を
middle_score内で、割り切れるか否かを判定するもの - より具体的には、判定にあたっては、制限時間（
remain_time）内にすべての風船を割れるか否かをTrue、Falseで返します - 1~6を繰り返してちょうどよい
middle_scoreを見つけて、それが答え
です。
最後の答えをprintする部分について、いつも「max_score」が答えなのかそれとも「min_score」が答えなのかを迷います。
そんな時は、とりあえずどちらもprintしてみて、サンプル入力であってるほうを採用しています。
今回はmax_scoreでした。
022. AtCoder Regular Contest 054 B - ムーアの法則
回答
def cal_time(x, P):
# 現在計算にP年かかるPCをx年後に使用してかかる時間を算出
return x + P * pow(2, -x/1.5)
if __name__ == "__main__":
tolerance = 10**(-8)
P = float(input())
bottom = 0
top = 10**18 + 1
while top - bottom > tolerance:
middle1 = (2 * bottom + top) / 3
middle2 = (bottom + 2 * top) / 3
if cal_time(middle1, P) < cal_time(middle2, P):
top = middle2
else:
bottom = middle1
print(cal_time(bottom, P))
普通に数学として解くのであれば微分して極小値をとる時間を求めればよいのでそこまで難しくないと思われます（現役学生であれば・・・）。
しかし、プログラムで解くとなるとやり方を知らなければ、なかなか難しいと思いました。
一方で、やることは二分探索とあまりかわらず、一度解けば何とかなりそう、と思いました。
解き方は三分探索です。
方針は、
- 目的となる関数
cal_time(x, P)を作成 - この関数の極小値となるxを探します
-
bottomとtopの2点間を徐々に縮めていき、ちょうどよい(誤差が許容範囲になる)箇所が求めたいxとなります - そのために
bottom側の三分点middle1とtop側のmiddle2を算出し関数cal_time(x, P)で大きさを比べます - 上記比較の結果、
bottom側とtop側で大きい値が算定されたほうをmiddleに置き換えます - 上記を繰り返し、許容される誤差になったら探索終了
- 最後に
bottom又はtopで時間を算出（誤差まで下げているのでどっちでもよい）し、それが答え
です。
023. JOI 2008 本選 3 - ダーツ
回答
import bisect
N, M = map(int, input().split()) # Nは的の区切り数（Pの要素数）、Mは得点を獲得する際のバー
# 得点の合計SがM以下の場合はS、M超の場合は0点になる -> ぎりぎりの合計値を出せばよい
P = [int(input()) for _ in range(N)] # 各的の点数
P.append(0) # 投げない場合の0点も含めておく
P.sort()
double_score_list = []
for p1 in P:
for p2 in P:
score = p1 + p2
if score > M: # 無駄なappendを防ぐ
break
double_score_list.append(score)
double_score_list.sort()
# 自分自身を二分探索する
answer = 0
for double_score in double_score_list:
target = M - double_score
max_i = bisect.bisect_left(double_score_list, target) - 1
score = double_score + double_score_list[max_i]
if score > M:
continue
answer = max(answer, double_score + double_score_list[max_i])
print(answer)
まず思いつくのは、与えられたPから獲得することができる得点のリストを作成し、Mを超えないちょうどよい得点を二分探索で探す方法です。
しかしこれではリストを作成するためにforループを4回まわす必要があり、Nが10**3であることを考えると間に合いそうにありません。forループを多くとも2つにまで減らす必要があります。
forループを2つに減らすことを考えると、4回投げることを2回ずつに分けて考えれば半分になりそうです。
投げない場合の点数を含めて、2回で獲得することができる得点のリストを作成し、それぞれの得点について2分探索でちょうどよい得点を探しにいけばよさそうです。
具体的な方針は、
- 投げない場合の得点（0点）も含めて、2回で獲得できる得点のリスト
double_score_listを作成する - この際、重複や
Mを超過するような得点をリストに含めないようにbreakを入れておく -
double_score_listのすべての要素について二分探索を行い、合計がM以下で最大となる得点を探す
です。