はじめに
今日は競技プログラミングにおける重要なアルゴリズムの一つ、bit全探索を解説する。bit全探索とは任意の整数を２進数表記することで、場合分けや組み合わせを全探索するアルゴリズムのことである。
例題
あなたは和菓子屋さんに来ました。商品$A$は全部で$N$種類、$A_1,A_2,...,A_N$存在します。あなたは商品を$0\leq i \leq N$の範囲で、それぞれ一つずつ購入することが出来ます。選び方は何通りありますか。
例題解説
高校数学を学んだことのある方ならすぐにわかると思うが、答えは$2^N$通りである。商品数を$N$と一般化しているため、ここでは$N=3$として考えてみよう。
表１ 8通りの選び方
| 10進数 | $A_1$ | $A_2$ | $A_3$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 |
| 7 | 1 | 1 | 1 |
表１は購入した商品を１、しなかった商品を０として表している。そして最左列の10進数表記に対し、右三列は左端の１０進数を二進数表記したものに等しい。よって商品が$N$個あるときの題意に沿った選び方は$2^N$通りで,bit全探索では$0 \leq x \leq 2^N-1$を満たす整数$x$の２進数を考えればよいことになる。
そしてもう一つ、重要になるのはどの位が１か否かを判定することである。$N=n$であれば$2^n-1$を二進数表記するとn桁の数になる。よって$1 \leq i \leq N$を満たす整数$i$において$i$桁目が1か否かを判定すればよいことが分かる。
ここでbit演算子というものを使う。
Pyhtonにおけるbit演算子
1.bin関数
bin(x)と入力すると左に0bがつけられた二進数表記を返す関数。
print(bin(6))
#0b110 と出力される
2.シフト
1.右シフト
$>>$ であらわす。指定した桁だけ右にずらして、最下位より先に押し出されたビットは消える。
print(5>>0) #5
print(bin(5>>0)) #0b101
print(5>>1) #2
print(bin(5>>1)) #0b10
print(5>>2) #1
print(bin(5>>2)) #0b1
2.左シフト
$<<$ であらわす。指定した桁だけ左にずらして、空いたビットには0が入る。
print(5<<0) #5
print(bin(5<<0)) #0b101
print(5<<1) #10
print(bin(5<<1)) #0b1010
print(5<<2) #20
print(bin(5<<2)) #0b10100
また、引数を１としたとき
print(1<<0) #1
print(bin(1<<0)) #0b1
print(1<<1) #2
print(bin(1<<1)) #0b10
print(1<<2) #4
print(bin(1<<2)) #0b100
$(1<<x) = 2^x$になることに気が付いただろうか。今回のbit全探索ではこの性質を利用する。
論理演算
論理積
集合でいうところの「かつ」「AND」と同じである。
具体的な演算は表２を参照。
表２ 論理積
| AND | 積 | 答え |
|---|---|---|
| 0&0 | $0\times0$ | 0 |
| 1&0 | $0\times 1$ | 0 |
| 1&1 | $1\times 1$ | 1 |
掛け算と一緒である。今回論理積を各桁の判定に用いる。
論理和
集合でいうところの「または」「OR」と同じである。
具体的な演算は表３を参照。
表３ 論理和
| OR | 和 | 答え |
|---|---|---|
| 0or0 | $0+0$ | 0 |
| 1or0 | $0+ 1$ | 0 |
| 1or1 | $1+ 1$ | 2 $\to$ 1 |
和が１を超えるものはすべて１とみなす。
以上を用いてbit全探索を行う
ABC 221-C
問題文に0に気を付けろといっているが、正直そこまで関係ない。
制約では$1\leq N \leq 10^9$となっているため、$N$の桁数は最大10桁である。
$N$を二つに分けるとはbit全探索で選んだ数字（すなわち１）と、選ばなかった数字（すなわち０）で分けるということである。そして最大値を取る際の分離の仕方としては文字列を昇順にソートして、後ろから選んでいく。
ここで非常に重要なことを述べようと思う。$0$から$2^N-1$までの整数を探索するため、bit全探索の時間計算量は$O(2^N)$となり、指数時間アルゴリズムとなる。$N=10$として全探索するだけで$O(10^3)$となってしまうため、制約の最大値が非常に小さいことが大きな特徴である。今回は$N\leq 10^9$であるが、調べるのは各桁の選び方のため桁数$x$について全探索するから、実質$x\leq10$となりbit全探索を用いることが出来る。
問題解決の方針としては$0\leq i \leq 2^N-1$を満たす整数$x$を二進数表記した時$j$桁目（$1 \leq j \leq N$）が1の時の数字を$r$と０の時の数字を$l$として分けて考える。そして$j$のループが終わるごとに、$r \leq l$ の最大値を更新していくという手順でコーディングする。
n = input() #文字列として標準入力
n = list(n) #リストに格納
n.sort() #昇順にソート
long = len(n) #桁数を確認
ans =0
for i in range(1<<long): #2進数表記で0 <= i <= 2^N-1
r =0
l =0
for j in range(long):
if i & (1 << j): #1<<j = 2^j iの二進数表記のj+1桁目が１の時
r = r * 10 + ord(n[long-1-j])-ord("0")
#後ろから順に見ていく ord("0") = 48より整数文字を整数値に変換できる
#print(r)
else: #1<<j = 2^j iの二進数表記のj+1桁目が0の時
l = l * 10 + ord(n[long -1-j])-ord("0")
#print(l)
ans = max(ans,r*l) #最大値を取る
print(ans)
条件分岐で$i$の二進数表記の$j+1$桁目が１であるか否かを判定している。またord()関数は文字を整数値に変換できる便利な関数である。ちなみにord(A)$=65$であることからアルファベットにも対応している。
サンプル１の123で考える。これはソートしても123のままである。例えばbin(i)=0b1の時を考える。0b1とはすなわち001のことであるから$j=0$に関して$r=3, l=0$となる。同様にして$j=1$に関しては$r=3, l = 0\times 10 + 2= 2$となる。最後に$j=2$に関しては$r=3, l = 1 + 2\times 10 = 21$となる。よって$l\leq r = 21 \times 3 =63$と求められる。
解説の始めに各桁に0があろうとなかろうと関係ないといったのは、元の$r$や$l$に0を加えるだけで何も変化しないからである。
ABC 289-C
昨日行われたコンテストのC問題。こちらは問題文に対し、ご丁寧な説明がなされている。
「$M$個の集合から 1 個以上の集合を選ぶ方法は $2^M-1$ 通りあります。」
もうbit全探索をしてくれと言っているようなもの。そして$M \leq 10$と制約の最大値が非常に小さい。問題の誘導に従って素直に解く。
「$1 \leq x\leq N$ を満たす全ての整数 $x$ に対して、選んだ集合の中に $x$ を含む集合が少なくとも 1 個存在する。」とは「$1 \leq x\leq N$ を満たす全ての整数 $x$ が、選ばれた集合の中に必ず含まれる」ことである。ここで集合の議論をする際「少なくとも...」と言われたら真っ先に余事象を考えるべきだ。すなわち題意はすべての選び方から「$1 \leq x\leq N$ を満たす全ての整数 $x$ が、選ばれた集合の中に必ず含まれていない」選び方を引いてあげればよい。当然選び方の列挙にはbit全探索を用いる。
また選んだ集合の中に$x (1 \leq x \leq N)$が含まれているかを探索するときの時間計算量は$O(N^2)= O(100)$程度であり、bit全探索の時間計算量は$O(2^N)=O(10^3)$であることから全体の計算量は$O(10^5)$程度で十分間に合う。
n,m = map(int,input().split())
d = [[]*n for _ in range(m)]
for i in range(m):
c = int(input())
a = list(map(int,input().split()))
d[i] = d[i] + a #集合を一つ一つリスト内に格納する
count2 =0 #答えを表す変数
for i in range(1 << m): #bit全探索
t =[]
count1 =0 #xが含まれていない選び方をカウントする
for j in range(m):
if i &(1 << j):
t += d[j] #j+1桁の値が１のときリストを連結していく
for k in range(1,n+1,1):
#1からnまでの数字がそれぞれリスト内に存在するか一つ一つ確認
if i not in t:
count1 +=1 #存在しない数字があったらカウント
#今考えているリスト内に１からnまでのすべての整数が存在していた時
if count1 ==0:
count2 += 1
print(count2)
このようにして選び方を全列挙し、そのときの二進数に対して処理を施していくのがbit全探索である。制約が極端なくらい小さいのですぐに判別できるはず。またどちらの問題もdifficultyは400程度である。次回はグラフの探索アルゴリズムの解説をする予定。