bit 全探索は、競技プログラミングにおいて非常に重要なテクニックの一つです。
「０」と「１」で表す２進数の考え方を使って、すべての組み合わせを試します。
このテクニックを使うことで、難しい問題を効率的に解決することができます。
この記事では、bit 全探索の基礎知識から具体例なコードも使ってわかりやすく解説します。
C++ のコードで bit 全探索について解説した記事もありますので、ぜひ参考にしてください。
bit とは
bit は、「０」と「１」で表す情報の最小単位です。
コンピュータでは、bit が電気信号の「オン」と「オフ」のように２つの状態で情報を管理しています。
たとえば、４ビットは連続した４桁の bit で「1011」のようなものです。
「1011」は、左から2番目の bit が 0 で、残りの bit が 1 であることを表しています。
このような bit の集合を使えば、複数のフラグの状態を表すことができます。
ビットでフラグを管理する
３ビットの「１０１」について考えてみます。一番左と、一番右が「１」で、真ん中が「０」です。
たとえば、「赤、青、黄」の３つのボールから何個か選ぶとき、３ビットで表す bit の「１」が選んだとき、「０」が選ばなかったときと考えることができます。
- bit が １：選ぶ
- bit が ０：選ばない
「１０１」だと「赤、青、黄」なので、一番左の赤のボールと、一番右の黄のボールを選んだと表現できます。
「００１」だと、一番右の黄のボールだけ選んだと表現できます。
bit 全探索とは
bit の集まりを使って、選ぶか選ばないかを管理することができました。
このように bit の集まりを使って、すべての組み合わせについて探索するのが bit 全探索です。
３つのボールからいくつか選ぶ組み合わせ
「赤、青、黄」の３つのボールから、いくつかのボールを選ぶときの組み合わせについて考えてみます。
この組み合わせは全部で８通りあります。そのときの bit の集まりで「選ぶ（１）」か「選ばない（０）」かの対応を表してみます。
- 選 ば な い：０ ０ ０
- 黄：０ ０ １
- 青 ：０ １ ０
- 青 黄：０ １ １
- 赤 ：１ ０ ０
- 赤 黄：１ ０ １
- 赤 青 ：１ １ ０
- 赤 青 黄：１ １ １
１つのボールについて「選ぶ」、「選ばない」の２通りの選び方があります。
- 赤のボール：「選ぶ」、「選ばない」の２通り
- 青のボール：「選ぶ」、「選ばない」の２通り
- 黄のボール：「選ぶ」、「選ばない」の２通り
全体の選び方としては、「２通り * ２通り * ２通り = ８通り」→「23 = 8」になります。
bit で考えると、すべて選ばないときの「０００」からすべて選ぶときの「１１１」までを試せば、すべての組み合わせについて列挙できます。
２進数
２進数は、「０」と「１」の２つの数字だけを使って数を表現します。
今回の「０００」や「１１１」などは２進数になります。私たちが普段使っているのは１０進数で、０から９までの数字を使って数を表現します。
さきほどの bit の集まり（２進数）を１０進数に変換すれば、次のようになります。
- 選 ば な い：０ ０ ０ → ０
- 黄：０ ０ １ → １
- 青 ：０ １ ０ → ２
- 青 黄：０ １ １ → ３
- 赤 ：１ ０ ０ → ４
- 赤 黄：１ ０ １ → ５
- 赤 青 ：１ １ ０ → ６
- 赤 青 黄：１ １ １ → ７
「０００」から「１１１」までのすべての組み合わせは、１０進数の「０」から「７」までを２進数に変換したものになります。
つまり、「０００」から「１１１」までを試したいときは、１０進数の「０」から「７」を２進数に変換すれば試すことができるわけです。
もし、ボールの数が４つになれば、選び方は「２通り * ２通り * ２通り * ２通り= １６通り」→「24 = 16」です。bit では、「００００」から「１１１１」（１０進数だと０から１５）までの組み合わせです。
ボールの数が５つだと「2 * 2 * 2 * 2 * 2 = ３２通り」→「25 = 32」。bit では、「０００００」から「１１１１１」（１０進数だと０から３１）まで。
ボールの数が５つだと「2 * 2 * 2 * 2 * 2 *2 = ６４通り」→「26 = 64」。bit では、「００００００」から「１１１１１１」（１０進数だと０から６３）まで。
このように、N 個の中からいくつか選ぶときの組み合わせは「2N 通り」の選び方があります。
コード
実際の bit 全探索のコードについて、見ていきます。
３つのボールの組み合わせについて、すべて列挙する Python のコードです。
# ３つのボール
ball = ['黄', '青', '赤']
# 選ぶボールの数
n = len(ball)
# 0 から 2 の n 乗までのループ ( 2**3 = 8 )
for i in range(2**n):
# 表示用（何番目の組み合わせか）
print(f'{i} : ',end='')
# n 個の中からどれが選ばれているか（どの bit が 1 なのか）
for j in range(n):
# 選ばれているとき
if i & (1 << j):
# 表示用（選ばれているボール）
print(ball[j], end=' ')
# 表示用（次の組み合わせのための改行）
print()
"""実行結果
0 :
1 : 黄
2 : 青
3 : 黄 青
4 : 赤
5 : 黄 赤
6 : 青 赤
7 : 黄 青 赤
"""３つのボールから選ぶ組み合わせは「０００」から「１１１」まで試せばよかったですね。
１０進数だと「０」から「７」になります。
0 から 7 まで繰り返すには次のように書きます。
# 0 から 7 まで繰り返す
for i in range(8):
print(i)
"""実行結果
0
1
2
3
4
5
6
7
"""３つのボールを選ぶ組み合わせは、23 = 8 通りです。Python で累乗は 「**」 を使うので、先ほどのコードは次のように書き換えられます。
# 0 から 7 まで繰り返す
for i in range(2 ** 3):
print(i)
"""実行結果
0
1
2
3
4
5
6
7
"""どの bit が 1 なのか
「０００」から「１１１」までは、試すことができるようになりした。
次は、どの bit が「１」なのか判定する必要があります。
「１１０」（１０進数だと「６」）のときについて考えてみます。
この bit について右から１bit ずつ判定するのが次のコードです。
# ボールの個数
n = 3
# 110 のとき
bit = 6
for j in range(n):
if bit & (1 << j): # 選ばれているとき
print(f'{j} : 1 です')
else: # 選ばれていないとき
print(f'{j} : 0 です')
"""実行結果
0 : 0 です
1 : 1 です
2 : 1 です
"""if bit & (1 << j)の部分で、各桁のビットが「１」かを判定しています。
（1 << j）は、左シフトです。「１」を左に「ｊ」だけずらします。
ここでは、ｊは０から２まで変化するのでｊに対する（1 << j）は次のようになります。
- ｊ＝０のとき、1 << ０ は「００１」
- ｊ＝１のとき、1 << １ は「０１０」
- ｊ＝２のとき、1 << ２ は「１００」
あとは「＆演算子」を使って、その桁が「１」かを判定します。
＆演算子
＆は、ビット演算子になります。
２つのビットについて、各ビットが両方とも「１」のときに「１」になります。
- ０ ＆ ０ ＝ ０
- ０ ＆ １ ＝ ０
- １ ＆ ０ ＝ ０
- １ ＆ １ ＝ １
たとえば、「１１０」＆「００１」は「０００」になります。
「１１０」＆「０１０」は「０１０」になります。
110
& 001
-----
= 000
110
& 010
-----
= 010つまり、選ばれたボール（bit が１）のときは、値は０以外になります。
Python では、if 文は「０」だと「False」と判定され、「０」以外の数値だと「True」になります。
そのため、選ばれているときは、if 文が True になるので処理が実行されます。
# ボールの個数
n = 3
# 110 のとき
bit = 6
for j in range(n):
if bit & (1 << j): # 選ばれているとき
print(f'{j} : 1 です')
else: # 選ばれていないとき
print(f'{j} : 0 です')
"""実行結果
0 : 0 です
1 : 1 です
2 : 1 です
"""ビット全探索のテンプレート
ビット全探索の基本的なコードは次のようになります。
# bit 全探索
for i in range(2**n):
for j in range(n):
if i & (1 << j):
選ばれているときの処理これを使って、次のような問題を解いてみましょう。
問題
A1,A2,・・・ANのN個の整数が与えられます。 これらの整数からいくつかを選んで、その総和がKとなるような選び方が存在するかを求めてください。
次の bit 全探索を使ったコードで、この問題を解くことができます。
# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))
# bit 全探索
answer = 'No'
for i in range(2**N):
sum = 0
for j in range(N):
if i & (1 << j):
sum += A[j]
if sum == K:
answer = 'Yes'
print(answer)AtCoder Beginner Contest 079 C – Train Ticket
ABC079 C – Train Ticket を bit 全探索で解いてみます。
問題概要
4 つの 0 以上 9 以下の整数 A, B, C, D が整理番号としてこの順に書かれています。
A op1 B op2 C op3 D = 7 となるように、op1, op2, op3 に + か – を入れて式を作って下さい。
考え方
4 つの数字の間に ＋ か – を入れて ７ になる式を出力すればいいです。
bit 全探索で、op1, op2, op3 の中から + を入れる位置をすべて試します。
次のようなコードで、3カ所から ＋ を入れる位置をすべて試せます。
# + を入れる位置の個数
N = 3
# bit 全探索
for i in range(2**N):
for j in range(N):
if i & (1 << j):
print('+', end='') # 選んだとき
else:
print('-', end='') # 選んでないとき
print() # 表示用の改行
"""実行結果
---
+--
-+-
++-
--+
+-+
-++
+++
"""これで、すべての ＋ と – のパターンが試せるので、あとは、計算するだけです。
# 入力
S = input()
# + を入れる位置の個数
N = 3
# bit 全探索
for i in range(2**N):
answer = S[0] # 出力用の文字列
sum = int(S[0]) # 計算した結果の変数
for j in range(N):
# + 演算子のとき
if i & (1 << j):
answer += '+' + S[j+1]
sum += int(S[j+1])
# - 演算子のとき
else:
answer += '-' + S[j+1]
sum -= int(S[j+1])
# 計算結果の確認
if sum == 7:
answer += '=7'
print(answer)
exit()まとめ
bit 全探索を使えば、「選ぶ」、「選ばない」のような２種類の選択をする探索が簡単にできます。
N 個の中からいくつか選ぶときの選び方は、2N 通りあります。
選ばないを「0」、選ぶを「1」で考えれば、2進数ですべての選び方を列挙することができます。
全探索を解説したこちらの記事も参考にしてください。
