Pythonで二分探索、

bisectの使い方

bisectというものを使います。bisect_left bisect_rightの2パターンがあり、leftは同じ要素が並んでいる際に一番左側に挿入し、rightは一番右端に挿入します。具体的に使い方を見てみましょう。

from bisect import bisect_left, bisect_right
A = [1, 2, 2, 3, 4]
indexR = bisect_right(A, 2)
indexL = bisect_left(A, 2)
print("indexR=", indexR)
print("indexL=", indexL)

出力結果は以下の通りです。indexというのは、リストのA[この数字]のことです。

indexR=3
indexL=1

リストの範囲を指定して行うこともできます。

indexL = bisect_left(A, 2, i, j)

この場合、インデックスがi以上j未満の範囲で判定を行ってくれます。

from bisect import bisect_left, bisect_right
A = [1, 2, 2, 3, 4]
indexR = bisect_right(A, 2, 2, 5)
indexL = bisect_left(A, 2, 2, 5)
print("indexR=", indexR)
print("indexL=", indexL)

例えば上のコードでは、{2, 3, 4}の範囲で判定を行うため、leftの場合には2の左側、rightは2の右側に挿入されます。出力結果は以下の通りです。

indexR= 3
indexL= 2

insortの使い方

insortは実際にリストに要素を挿入してくれるものです。bisectと同様には左右や範囲の指定が出来ます。

from bisect import insort_left, insort_right
A = [1, 2, 2, 3, 4]
insort_right(A, 2)
print(*A)

出力結果は以下の通りです。

1 2 2 2 3 4

bisectを使ってABC172Cを解く

atcoder.jp

from bisect import bisect_left, bisect_right
n, m, k = map(int, input().split())
A = list(accumulate(map(int, input().split())))
B = list(accumulate(map(int, input().split())))
A=[0]+A
B=[0]+B
ans = []
for i in range(n+1):
    c = bisect_right(B, k-A[i])-1
    if c!=-1:
        ans.append(c+i)
print(max(ans))

　accumulateというのは、累積和を取ってリストに代入してくれるものです。つまり、A[i]=A[i-1]+A[i]といった具合になります。ちなみに、リストのインデックスが本を何冊読んだかに対応しています。例えばA[3]は本棚Aの本を３冊読んだ時にかかる時間になっています。そのため、リストAB両方に本をゼロ冊読んだ時にかかる時間を追加しています。
　上のコードでは、本棚Aの本を０～N冊読んだ時に、本棚Bの本を何冊読めるか？を全探索しています。最終的に、その読める冊数をリストansに記録して、最大値を求めます。