はじめに

今日は競技プログラミングにおける重要なアルゴリズムの一つ、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程度である。次回はグラフの探索アルゴリズムの解説をする予定。