【AtCoder】Pythonでビット探索

2021.06.16

2024.03.24

競技プログラミング

AtCoderPython

はじめに

ビット探索について、どんなものなのか、AtCoderなどではどんな問題で使うのか、Pythonで実装するためのサンプルコードについて紹介していきます。

実際のAtCoderで利用したプログラムも掲載しています。

ビット探索とは

ビット探索は、n個のものに対して選ぶ/選ばないやon/offなどの2通りがあるような場合に、全通りである $2^n$ 通りを探索することです。

下記の画像の場合は $n=5$ になるので、全部で32通りになります。

それぞれ2通りあるので、選ぶ/選ばないを0と1で表し、全体を2進数で表すことができます。

実装する場合には、0から $2^n-1$ までの10進数を2進数で表し、各ビットの0/1で探索していきます。

使いどころ

AtCoderなどでは以下の状況でビット探索が有効です。

選ぶ/選ばないやスイッチのon/offなどそれぞれの候補に対して2通りのパターンがある
全体の数であるNがそれほど大きくない

ビット探索のサンプルコード

ビット探索の基本となるサンプルコードです。

前提として、ビット単位演算とシフト演算の知識が必要になります。ビット単位演算とシフト演算については下記で説明しています。

Pythonでビット単位演算とシフト演算

AtCoderでよく使うような2進数を使った演算をまとめています。 2進数の表し方まずはPy

1n = 3
2
3patterns = []
4# 0~2^n-1をループして2^n通りを試す
5for i in range(2**n):  # 1<<nとしているプログラムもある
6    p = [0] * n
7    for j in range(n):
8        # 0からn-1までjで右シフトして1とのANDをとることでビットが立っているか(1かどうか)判定
9        if i >> j & 1: # if i & (1 << j): # これでも可
10            p[j] = 1
11    patterns.append(p)
12
13print(patterns)

実行すると全てのパターンが列挙されていることがわかります。

1[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0],
2 [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]]

一番わかりにくいのは下記のコードかと思います。(私はそうでした)

1if i >> j & 1:

簡単に言えば $i$ を2進数と考えた時、下から $j$ 桁目が1になっているかを判定しています。

サンプルコードの全体から考えると、探索の全パターンとなる $i(0 \leq i \leq 2^n)$ を $j$ で0から $n-1$ まで桁をずらしながらビットが立っているか（1になっているか）を判定していることになります。

AtCoderのサンプル問題

ABC128 C問題

C - Switches

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

スイッチのon/offのパターンを列挙して、条件を満たす組み合わせを求める問題です。

ビット探索でパターンを求めてから、条件に当てはまるか判定しています。

1n, m = map(int, input().split())
2k = []
3s = []
4for _ in range(m):
5    tmp = list(map(int, input().split()))
6    k.append(tmp[0])
7    s.append(tmp[1:])
8p = list(map(int, input().split()))
9
10ans = 0
11for i in range(2**n):
12    switch = [0] * n
13    # スイッチのon/offのパターンをビット探索で
14    for j in range(n):
15        if(i >> j) & 1:
16            switch[j] = 1
17
18    # 全ての電球が点灯するか
19    check = True
20    for j in range(m):
21        k_sum = 0
22        for s_i in range(k[j]):
23            k_sum += switch[s[j][s_i]-1]
24        if k_sum % 2 != p[j]:
25            check = False
26            break
27    if check:
28        ans += 1
29
30print(ans)

ABC147 C問題

C - HonestOrUnkind2

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

「正直者」と「不親切な人」のパターンをビット探索で列挙して、それぞれの証言と矛盾していないか判定しています。

1n = int(input())
2A = []
3X = []
4Y = []
5for _ in range(n):
6    a = int(input())
7    A.append(a)
8    x = []
9    y = []
10    for _ in range(a):
11        _x, _y = map(int, input().split())
12        x.append(_x-1)
13        y.append(_y)
14    X.append(x)
15    Y.append(y)
16
17
18ans = 0
19# ビット探索で正直者を仮定する
20for i in range(2**n):
21    check = True
22    honest = []
23    for j in range(n):
24        # 正直者だけ矛盾してないか判定
25        if (i >> j) & 1:
26            honest.append(j)
27            for k in range(A[j]):
28                if Y[j][k] != ((i >> X[j][k]) & 1):
29                    check = False
30                    break
31
32    if check:
33        ans = max(ans, len(honest))
34
35print(ans)

ABC197 C問題

C - ORXOR

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

数列の間に区切りを入れる/入れないでビット探索でパターンを列挙して、全通りを試して最小値を求めています。

1n = int(input())
2A = list(map(int, input().split()))
3
4ans = 2**30
5
6# 区切る箇所をビット探索で
7for i in range(2**(n-1)):
8    or_ = 0
9    xor = 0
10    for j in range(n):
11        or_ |= A[j]
12        # 区切る箇所がきたら
13        if (i >> j) & 1:
14            xor ^= or_
15            or_ = 0
16    xor ^= or_
17    ans = min(ans, xor)
18
19print(ans)