bit全探索の基本問題解説[Python]　AtCoder 221-C, 289-C 

# はじめに
 今日は競技プログラミングにおける重要なアルゴリズムの一つ、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がつけられた二進数表記を返す関数。
```Python
print(bin(6))
#0b110 と出力される
```

### 2.シフト
#### 1.右シフト
$>>$ であらわす。指定した桁だけ右にずらして、最下位より先に押し出されたビットは消える。

```Python
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が入る。

```Python
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
```
また、引数を１としたとき
```Python
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
https://atcoder.jp/contests/abc221/tasks/abc221_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$ の最大値を更新していくという手順でコーディングする。

```Python
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
https://atcoder.jp/contests/abc289/tasks/abc289_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)$程度で十分間に合う。

```Python
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程度である。次回はグラフの探索アルゴリズムの解説をする予定。