【AtCoder】bisectでリストを二分探索する

2021.09.10

2024.03.24

競技プログラミング

bisectPython二分探索

はじめに

bisectの使い方とbisectを使うAtCoderの問題をまとめました。

bisectの使い方

bisectは、ソートされたリストにソートされた状態を保ちながら挿入、挿入する場所を求めることができるライブラリです。

二分探索を利用しているため効率よく挿入する場所を見つけることができます。挿入する場所の探索は $O(\log n)$ で行えます。

挿入自体の操作は $O(n)$ かかることに注意してください。

挿入できる場所を求める

bisect_leftは、挿入できるリストの添字を返します。同じ値がある場合は、その値の最も左側の添字になります。

1li = [2, 5, 8, 13, 13, 18, 25, 30]
2
3ind = bisect.bisect_left(li, 10)
4print(ind)
5
6ind = bisect.bisect_left(li, 13)
7print(ind)

以下のようにソートされた状態を保ちながら挿入できる添字を返します。

13
23

bisect_rightとbisectは、挿入できるリストの添字を返します。同じ値がある場合は、その値の最も右側の添字になります。

1li = [2, 5, 8, 13, 13, 18, 25, 30]
2
3ind = bisect.bisect_right(li, 10)
4print(ind)
5
6ind = bisect.bisect_right(li, 13)
7print(ind)
8
9ind = bisect.bisect(li, 10)
10print(ind)
11
12ind = bisect.bisect(li, 13)
13print(ind)

以下のようにソートされた状態を保ちながら挿入できる添字を返します。

挿入する

bisectではリストに挿入もできます。ただし、挿入自体の操作は $O(n)$ かかります。

insort_leftはリストに値を挿入します。同じ値がある場合は最も左側に挿入します。

1li = [2, 5, 8, 13, 13, 18, 25, 30]
2bisect.insort_left(li, 13)
3print(li)

1[2, 5, 8, 13, 13, 13, 18, 25, 30]

insort_rightとinsortはリストに値を挿入します。同じ値がある場合は最も右側に挿入します。

1li = [2, 5, 8, 13, 13, 18, 25, 30]
2bisect.insort_right(li, 13)
3print(li)

1[2, 5, 8, 13, 13, 13, 18, 25, 30]

insortも同じ動きをします。

1li = [2, 5, 8, 13, 13, 18, 25, 30]
2bisect.insort(li, 13)
3print(li)

1[2, 5, 8, 13, 13, 13, 18, 25, 30]

AtCoderのサンプル問題

ABC130 D問題

D - Enough Array

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

長さNの数列Aと整数Kが与えられ、Aの連続する部分列でその要素の和がK以上となるものはいくつあるのか求める問題です。

累積和を求めてから、bisectで挿入できる場所を探索します。

1import bisect
2import itertools
3
4n, k = map(int, input().split())
5a = list(map(int, input().split()))
6X = [0] + list(itertools.accumulate(a))
7ans = 0
8
9for x in X:
10    ind = bisect.bisect_left(X, k+x)
11    if ind <= n:
12        ans += n - ind + 1
13
14print(ans)

ABC205 D問題

D - Kth Excluded

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

長さNの数列AとQ個の $K_{i}$ が与えられ、数列A含まれない $K_{i}$ 番目の整数を求める問題です。

数列のそれぞれの値以下で選べる整数の個数のリストを作成して、bisectで挿入できる場所から $K_{i}$ 番目の整数を求めます。

1import bisect
2
3n, q = map(int, input().split())
4A = list(map(int, input().split()))
5K = []
6for _ in range(q):
7    K.append(int(input()))
8
9A.sort()
10
11B = [A[0]-1]
12for i in range(1, len(A)):
13    B.append(A[i]-A[i-1]+B[i-1]-1)
14
15for k in K:
16    if B[-1] < k:
17        print(A[-1] + k - B[-1])
18    else:
19        ind = bisect.bisect_left(B, k)
20        print(A[ind] - 1 - (B[ind] - k))