bit全探索の利用【競技プログラミング】

# はじめに
- bit全探索って、[ニブタン](https://qiita.com/kei_tnk/items/85d14f6c835b83f1ed07)並みにメジャーな解法だと思うけど、bit全探索をタイトルにした投稿をしてなかったから、しておこうと思う。なお、bit全探索は投稿の一部としては、[ナップサック問題の解法の一つ](https://qiita.com/kei_tnk/items/1cb21b9160fe8d0e677d#bit%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)で書いてる。

# bit全探索を使わないと...
- 実は、以前書いた投稿[知識ゼロからAtCoderにチャレンジしてみた話【c++の豆知識とAtCoderの流儀のお勉強】後編](https://qiita.com/kei_tnk/items/13344cc8b13e4c79aa34)でも書いてたんだけど、まずはbit全探索のありがたみを知るために、bit全探索なしだと、どれだけ面倒くさいかを実感して欲しい。
- 例えば、サイズnの整数配列vsがあったとして、その要素のいくつかを合計して、特定の数値mを作れるかどうか？という問題について、bit全探索を使わずに解いてみる。
- 例えば、サイズが5の時は、以下のコードで解ける。まあ、n=5しか対応していないから、「解ける」と言ったら怒られそうだけど。
```swift
let (_,m) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)!}

var ans = "No"

OUT:for i0 in 0...1 {
    for i1 in 0...1 {
        for i2 in 0...1{
            for i3 in 0...1{
                for i4 in 0...1{
                    if i0*vs[0] + i1*vs[1] + i2*vs[2] + i3*vs[3] + i4*vs[4] == m {
                        ans = "Yes"
                        break OUT
                    }
                }
            }
        }
    }
}

print(ans)
```
- 入力例は
```
//例1
5 13
3 4 5 7 8 // 結果はYes 5+8=13

//例2
5 13
3 4 5 7 11 // 結果はNo
```
- まあ解けたけど、不格好だよね。可読性も低いし。変数やfor文の大量発生とか、嫌すぎる。

# bit全探索の場合
- これをbit全探索を使って書く場合の基本形は以下のとおり。
```swift
for bf in 0..<(1<<n) { // bit全探索のフラグ管理だから、bitFlag ⇒ bf
    
    // bf毎の初期化


    // bit位置毎の処理
    for i in 1...n { // 左から数えたbitの位置
        if (bf >> (n-i)) & 1 == 0 { // 左からibit目のビットが「0」or「1」
        
        // bitが0の時の処理
        
        } else {

        // bitが1の時の処理

        }
    }
        
    // bf毎の後処理
    
}
```
- 最初の行の`1<<n`は、1を2進数換算でn bit左シフトした数値となる。例えば、n=5のとき、つまり`1<<5`は0b100000( = 2^5 = 32)となる。よって、`bf in 0..<(1<<5)`は、`bf in 0b00000...0b11111`と同義となる。よって、for文を32回、回すこととなる。AtCoderでは、$10^8$程度までの計算量にしか対応していないから、bit全探索が使えるnは22程度となる。n=22のとき、外側のfor文の回転数は$2^{22}$ = 4.2e6だから、まだ余裕があるように思えるけど、内側のfor文でもn回回しているから、計算量は$22×2^{22}$ = 0.9e8となる
- 最初のbit全探索を使わないコードでは、配列の最初の要素を含むか含まないかについては、変数i0を用意して、それを0or1に変化させて対応させた。
- bit全探索では、配列の最初の要素を含む含まないについて、for文の変数bfの変化範囲0b00000〜0b11111のうち、いちばん左のbit「0b<font color="red">●</font>????」で表現し、2番目の要素については、左から2番目のbit「0b?<font color="red">●</font>???」で表現する。
- 上記コードの内側のfor文の、`i in 1...n`におけるiは左から数えたbit位置を示す。
- if文の `(bf >> (N-i)) & 1 == 0`は、左からibit目のビットが「0」or「1」を判定している。
- ちなみに、配列の最初の要素を一番右のbit「0b????<font color="red">●</font>」で表現し、2番目の要素を右から2番目のbit「0b????<font color="red">●</font>?」で表現することも出来るけど、その場合は、for文の範囲は`i in 0..<n`とし、if文の条件式は`(bf >> i) & 1 == 0`に変更する。こちらの方がコードは綺麗だけど、配列のいちばん「左」（index:0）の要素が、bfのbitの一番「右」に対応するから、場合によっては頭が混乱するんだよね。
- さて、配列vsの要素を組み合わせた合計でmにすることが出来るかどうかのコードは、次のとおり。
```swift
let (n,m) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)!}

var ans = "No"

OUT:for bf in 0..<(1<<n) { // bit全探索のフラグ管理だから、bitFlag ⇒ bf
    
    // bf毎の初期化
    var sum = 0 // --- ①

    // bit位置毎の処理
    for i in 1...n { // 左から数えたbitの位置
        if (bf >> (n-i)) & 1 == 0 { // 左からibit目のビットが「0」or「1」
        
        // bitが0の時の処理
        // このコードでは何もしない
        
        } else {

        // bitが1の時の処理
        sum += vs[i-1] // bitの位置と、配列のindexは1ズレる --- ②
        if sum == m {ans = "Yes";break OUT} // --- ③

        }
    }
        
    // bf毎の後処理
    // 特になし
    
}

print(ans)
```
- bit全探索の基本形に①②③の3行を追加しただけで完成！

# 最後に
- つい先日、[ナップサック問題を分枝限定法で解く投稿](https://qiita.com/kei_tnk/items/00b573ac7c9c853f3939)を書いたけど、そんな滅多に出ない問題の解法を書いてるくせに、bit全探索を書いてなかったなんて、反省だな。
- 自分の脳味噌への知識定着のためにも、基本をおろそかにせずに、投稿していきたい。

# おまけ（左からではなく、下位ビットから処理する場合のコード）
- こっちの方がシンプルだから、一応書いておきます。
```swift
for bf in 0..<(1<<n) { // bit全探索のフラグ管理だから、bitFlag ⇒ bf
    
    // bf毎の初期化


    // bit位置毎の処理
    for i in 0..<n {
        (bf >> i) & 1 == 0 { // bfの下位ビットから処理
        
        // bitが0の時の処理
        
        } else {

        // bitが1の時の処理

        }
    }
        
    // bf毎の後処理
    
}
```