はじめに
ビット探索について、どんなものなのか、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がそれほど大きくない
ビット探索のサンプルコード
ビット探索の基本となるサンプルコードです。
前提として、ビット単位演算とシフト演算の知識が必要になります。ビット単位演算とシフト演算については下記で説明しています。
n = 3
patterns = []
# 0~2^n-1をループして2^n通りを試す
for i in range(2**n): # 1<<nとしているプログラムもある
p = [0] * n
for j in range(n):
# 0からn-1までjで右シフトして1とのANDをとることでビットが立っているか(1かどうか)判定
if i >> j & 1: # if i & (1 << j): # これでも可
p[j] = 1
patterns.append(p)
print(patterns)実行すると全てのパターンが列挙されていることがわかります。
[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0],
[0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]]一番わかりにくいのは下記のコードかと思います。(私はそうでした)
if i >> j & 1:簡単に言えば\(i\)を2進数と考えた時、下から\(j\)桁目が1になっているかを判定しています。
サンプルコードの全体から考えると、探索の全パターンとなる\(i(0 \leq i \leq 2^n)\)を\(j\)で0から\(n-1\)まで桁をずらしながらビットが立っているか（1になっているか）を判定していることになります。
AtCoderのサンプル問題
ABC128 C問題
スイッチのon/offのパターンを列挙して、条件を満たす組み合わせを求める問題です。
ビット探索でパターンを求めてから、条件に当てはまるか判定しています。
n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
tmp = list(map(int, input().split()))
k.append(tmp[0])
s.append(tmp[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
switch = [0] * n
# スイッチのon/offのパターンをビット探索で
for j in range(n):
if(i >> j) & 1:
switch[j] = 1
# 全ての電球が点灯するか
check = True
for j in range(m):
k_sum = 0
for s_i in range(k[j]):
k_sum += switch[s[j][s_i]-1]
if k_sum % 2 != p[j]:
check = False
break
if check:
ans += 1
print(ans)ABC147 C問題
「正直者」と「不親切な人」のパターンをビット探索で列挙して、それぞれの証言と矛盾していないか判定しています。
n = int(input())
A = []
X = []
Y = []
for _ in range(n):
a = int(input())
A.append(a)
x = []
y = []
for _ in range(a):
_x, _y = map(int, input().split())
x.append(_x-1)
y.append(_y)
X.append(x)
Y.append(y)
ans = 0
# ビット探索で正直者を仮定する
for i in range(2**n):
check = True
honest = []
for j in range(n):
# 正直者だけ矛盾してないか判定
if (i >> j) & 1:
honest.append(j)
for k in range(A[j]):
if Y[j][k] != ((i >> X[j][k]) & 1):
check = False
break
if check:
ans = max(ans, len(honest))
print(ans)ABC197 C問題
数列の間に区切りを入れる/入れないでビット探索でパターンを列挙して、全通りを試して最小値を求めています。
n = int(input())
A = list(map(int, input().split()))
ans = 2**30
# 区切る箇所をビット探索で
for i in range(2**(n-1)):
or_ = 0
xor = 0
for j in range(n):
or_ |= A[j]
# 区切る箇所がきたら
if (i >> j) & 1:
xor ^= or_
or_ = 0
xor ^= or_
ans = min(ans, xor)
print(ans)
