想定している読者
以下のような方に向けた記事になっています。
- Pythonを使って競技プログラミングに取り組んでいる
- ビット全探索という言葉は聞いたことがあるけれどまだ実装はできない
- ビット全探索を用いたコードを見たことはあるが解読が困難
- （少なくとも一度は）ライブラリを使わずにビット全探索を実装してみたい
ビット全探索を自力で実装することに主眼を置いた記事になっていることに注意してください。
便利なライブラリを用いて簡単にビット全探索を行いたい方はPythonの便利な標準ライブラリであるitertoolsを利用した方法を調べてみてください。
また、そもそもビット全探索の考え方がわからない方は先に別の記事を読むことをお勧めします。
ビット演算
この章では、ビット全探索の実装に不可欠なビット演算について理解することを目的としています。
ビットAND
&の左辺と右辺両方のビットが1であるとき、1を返します。
12 & 10
-- Output --
8
12を2進数に変換すると 0b1100 になります（0bは2進数であることを意味します）。
10を2進数に変換すると 0b1010 です。
それぞれの位を比較したときに、左辺と右辺の両方とも1になっている場合にのみ1が返ってくることを考えると、この2数のビットANDをとった結果は 0b1000 になります。
0b1000 を10進数に変換すると８になるので、Outputとして8が得られます。
以下参考になるかもしれないので載せておきます。
print('12 : {0} \n10 : {1} \n08 : {2}'.format(bin(12), bin(10), bin(12 & 10)))
-- Output --
12 : 0b1100
10 : 0b1010
08 : 0b1000
左シフト
<<の左辺の値を右辺の値だけ左にシフトします。
5 < < 2
-- Output --
20
5 = 0b101 であり, これを2ビット左にシフトすると 0b10100 = 20 となります。
ここまでの知識を用いて以下コードの意味がわかるか確かめてみましょう。
後ほど出てきます。
1 << 3 は1を3だけ左にシフトしたものだから 8 になることがポイントです。
for bit in range(1 < < 3):
print(bit)
-- Output --
0
1
2
3
4
5
6
7
ビット全探索
ビット bit に i 番目のフラグが立っているかどうかを調べるときは if(bit & (0 << i)) を用います。
噛み砕いて言うと、bit という変数の値を2進数に変換したときに 2^{n - i} の位が1であるか、を調べています。
check = 12
n = len(bin(check)) - 2 # checkを2進数表記したときの桁数（0bの2文字は取り除く）
print(bin(check))
for i in range(n):
# 1を i だけ左シフト
if(check & (1 < < i)): # (check & (1 < < i))==1 ならTRUE
print('yes')
else:
print('no')
-- Output --
0b1100
no
no
yes
yes
次の様に 2^{n} 通りの全パターンを出力することができます。
n = int(input('n = '))
for bit in range(1 < < n):
b = []
for i in range(n):
if (bit & (1 < < i)):
b.append('〇')
else:
b.append('×')
print(b)
-- Output --
n = 4
['×', '×', '×', '×']
['〇', '×', '×', '×']
['×', '〇', '×', '×']
['〇', '〇', '×', '×']
['×', '×', '〇', '×']
['〇', '×', '〇', '×']
['×', '〇', '〇', '×']
['〇', '〇', '〇', '×']
['×', '×', '×', '〇']
['〇', '×', '×', '〇']
['×', '〇', '×', '〇']
['〇', '〇', '×', '〇']
['×', '×', '〇', '〇']
['〇', '×', '〇', '〇']
['×', '〇', '〇', '〇']
['〇', '〇', '〇', '〇']
練習問題 〜ABCの過去問題より〜
ここまでの内容を習得することで、実装に必要な知識は揃ったのではないでしょうか。
これから練習問題に取り組んでみましょう。
掲載した問題は全てABC(AtCoder Beginner Contest)で出題された問題です。
ネタバレにより悲しい気持ちになる人が少なくなるよう古めの問題を2問用意しました。
ABC 045 C問題 - たくさんの数式
問題はこちらです。以下問題の引用です。
【問題文】
1 以上 9 以下の数字のみからなる文字列 S が与えられます。
この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。
一つも入れなくてもかまいません。
ただし、+ が連続してはいけません。
このようにして出来る全ての文字列を数式とみなし、和を計算することができます。
ありうる全ての数式の値を計算し、その合計を出力してください。
【制約】
- 1 \leq |S| \leq 10
- S に含まれる文字は全て
1〜9の数字
S = input() #l桁の数字を文字列型で入力
l = len(S) # 文字列の長さ
n = l - 1 # 文字列の間の数
ans = 0
for bit in range(1 < < n): # 0から((1をnだけ右シフトした数)-1)までのfor文
s = S[0]
for i in range(n):
if (bit & (1 < < i)): # 0から(2^n - 1)までのfor文
s += '+'
s += S[i +1]
ans += sum(map(int, s.split('+')))
print(ans)
-- Output --
125
176
【補足コメント】
1 < < n は「1をnだけ右シフトした数」なので 2^{n} になります。
なので、 for bit in range(1 < < n): で 2^{n} 通りを全探索することができます。
二重ルーブの内側にある繰り返し for i in range(n): は各桁を調べるためのfor文で、その一行下のif文でフラグが立っているか調べています。
ABC 079 C - Train Ticket
問題はこちらです。以下問題の引用です。
【問題文】
駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。
切符には 4 つの 0 以上 9 以下の整数 A,B,C,D が整理番号としてこの順に書かれています。
A op1B op2 C op3 D = 7 となるように、op1, op2, op3 に + か - を入れて式を作って下さい。
なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。
【制約】
- 0 \leq A,B,C,D \leq 9
- 入力は整数からなる
- 答えが存在しない入力は与えられない
abcd = input() #4つの数字をstr型で入力
l = len(abcd) # l=4
for bit in range(1 < < l - 1):
N = abcd[0]
for i in range(3):
N += ' '
if ((bit > > i) & 1):
N += '-'
else:
N += '+'
N += abcd[i +1]
N += ' '
#print(N)
N_int = sum(map(int, N.split()))
#print(N_int)
if N_int == 7:
#ans = list(map(str, N.split()))
ans = N.replace(' ', '')
print('{}=7'.format(ans))
break
-- Output --
1222
1+2+2+2=7
【補足コメント】
整数が4つ与えられることと、4つの整数が全て1桁であることを考えると本来 l は不要です。
最後に
ビット全探索の実装はできるようになりましたか？
コードの理解と実装ができるようになれば、競技プログラミングの中で新しいビット全探索の問題と遭遇した際も解けるようになっているはずです。
今回書いたコードをすぐに取り出せるようにして、コピペ＆アレンジしても良し、記事冒頭で触れた便利なライブラリを使うも良し、皆さんがコンテスト中に自力でビット全探索の問題を解けることを願っています。
