bit全探索をまとめてみた

# はじめに
こんにちは。takumikanです。
今回は**bit全探索**について個人的に学習したことをメモがてらまとめます。
問題や内容は逐次修正していきたいと思っています!!

# 目次
[1. bit全探索とは](#bit全探索とは)
[2. 実装](#実装)
[3. 例題](#例題)

## bit全探索とは
bit全探索とは、一言でいえば、**全探索を行う実装の一つ**である。(そのまま)
といってもよくわからないので、具体例をみていきます。

例えば、以下のような問題を考えます。
> 10円,50円,100円を1枚ずつ用いて払える金額を求めよ。

このとき、単純な解法として、
それぞれ「使う」「使わない」の2通りずつ、計$2^3 = 8$通り考えられる(以下の図参照)

<img width="600" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/79661851-1ae0-c0ec-09eb-5404dbb87064.png">

一番上の行は、全て×なので、1枚も硬貨を使用しない = 0円
二番目の行は、100円のみ使用する = 100円
三番目の行は、50円と100円を使用数 = 50 + 100 = 150円
ということを表しています。

つまり、"10円,50円,100円を1枚ずつ用いて払える金額を求める"には、
"**使うか使わないかの全組み合わせ(各行に対応)を求める**"ことが出来れば良いことがわかります
(写真の全ての○×の組み合わせを求められればあとは1行ずつ金額を求めるだけ)

ちなみに、プログラム上では、"◯と×"は
"**1と0**"または"**trueとfalse**"で表します。
今回は0と1の組み合わせで求めることにします(下図参照)
<img width="300" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/79661851-1ae0-c0ec-09eb-5404dbb87064.png"> <img width="300" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/6f619c4c-dab7-5461-3405-6f2b36f715d2.png">

それでは、この0と1の組み合わせをどのようにして求めれば良いのか。
この"**0と1の全組み合わせ(各行)を求める**"方法の一つがまさにbit全探索となります。

**さらに**
この0と1の列を眺めていると、2進数として見ることができますね(できない)
つまり、この各行を2進数と見れば、以下のようになります
<img width="500" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/934f0037-139b-f1d0-6d1c-e67753ee8d13.png">

ここまでをまとめると、
- 要素がN個(この例では10,50,100円の3個)の場合は$2^{N}$の組み合わせがある。
- それぞれを使う使わないで0と1に分けると、各行が$0$ ~ $2^{N}-1$に対応する。
    - 0が最初にあるため、$2^N$にならないことに注意(硬貨の例では最後は8ではなくて7)




## 実装
それでは、早速実装の方を見ていきましょう。
はじめに、実装の全体図を示します。
```c++
for (int bit=0; bit<(1<<N); bit++){
        vector<int> use(N, 0);
        for (int j=0; j<N; j++){
            if (bit & (1<<j)) use[j]=1;
        }
        // useは[0, 0, 1]のような(各行のどれか)が作成できる
        // useを使った何らかの処理
    }
```

たったこれだけです。(笑)
※ Nは要素の数(最初の例では硬貨の数=3)を表しています

色々見慣れない(自分だけか)実装が出てきたので、1行ずつまとめます。
1. ```1<<N```について
    詳しく知りたい方は、"シフト演算"で調べてみてください。今回は簡単に紹介します
    一言でまとめると、「1をN個だけ右にずらすこと」を表しています。
    具体例の方がわかりやすいので、具体例を示します。 
    1<<0 : $1_{(2)}$ = 1
    1<<1 : $10_{(2)}$ = 2
    1<<2 : $100_{(2)}$ = 4
    1<<3 : $1000_{(2)}$ = 8
    1<<N : $100.....00_{(2)}$ = $2^{N}$
    例えば、N=3の場合は1<<3=$100_{(2)}$$=8$を表します。(2進数で"=X"を求めていることに注意)
    
1. 1行目: ```for (int bit=0; bit<(1<<N); bit++)```
    このfor文が示しているのは、bit$=0$ ~ $2^{N}-1$までのループ
    すなわち、各行を2進数としてみたときの数字(紫の数字)を1つずつbitに代入しています。
    <img width="400" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/934f0037-139b-f1d0-6d1c-e67753ee8d13.png">
    
1. 2行目: ```vector<int> use(N,0);```
    単純に、使うか使わないか(１か0か)を格納するvectorを作成しています。
    つまり、各ループ(各行)ごとにuseを作成しています。
    最初は全要素(硬貨の例では3要素)は0で初期化しています。
    最終的な目標はこの**useの要素のうち使用する部分を1にすること**になります
    (下の画像の場合はuseの最後の要素を1に変更することになります)
    <img width="400" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/1c54e03a-8ae9-31b3-c540-a2b54ee3cca6.png">

1. 3行目: ```for (int j=0; j<N; j++)```
    単純にjに0からN-1(=要素数-1)を代入しています。
    硬貨の例では、N=3なので、0~2を代入します。

1. `&`について
    シフト演算と同様に詳しく知りたい方は「ビット演算」で検索してみてください。
    ここでは、`X&Y`はXとYを2進数としてみて、andをとった結果を表す。と留めておきます
    具体的には、以下の図に示します。
    <img width="600" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/722ac1f5-213c-e624-e72c-91a32de554eb.png">

    
1. 4行目: ```if (bit & (1<<j)) use[j]=1;```
    確認です。useの目的はなんだったでしょうか。
    useの最終的な目的は、1と0の組み合わせ(各行)の1の部分の要素を1にすることでした。
    (例: 2行目の場合 [0,0,0] (初期化時) -> [0,0,1]にする)
    つまり、結論から言うと、最後のこの部分で行っているのは、
    **初期化したuse=[0,0,0]のうち、使用する部分を1に変える**ことです
    
    
    それでは具体的にみていきます。まずは2行目(以下)を例とします
    <img width="600" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/94517474-569f-caeb-e193-729608589a16.png">

    bitが表しているのは、各行を2進数と見た時の数字(紫の数字)。つまり1でした。
    従って、**useの最後の要素を1に変換することが目標となります**
    
    jは3行目より0~Nの繰り返し、今回の例では0~2です。
    つまり、```1<<j```は1を左に１ずつずらしていくことを表します。(1, 10, 100, ...)
    従って、```(bit & (1<<j))```が表しているのは、
    **bitの各桁が１かどうかの確認を行っているだけ**です。
    具体的に、j=0,1,2の時の挙動を以下に示します。
    <img width="400" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/d4a5d555-35d9-b211-3df7-347416430cf4.png">
    <img width="400" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/9cb412ba-4873-91f0-b4fd-1f6e875fb239.png">
    <img width="400" alt="example.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2515824/ac696104-ae7e-1c47-b509-fbbc3d8bcdfc.png">
    
    流れをまとめると以下のようになります。
    - bit=0~$2^N-1$のそれぞれに対して、
     j=0~N-1で```1<<j```とbitでand演算を行うことにより、bitの1の部分を取り出す
    - useが各ループごとに、各行に対応する1と0の組み合わせとなる。
    
    従って、あとは、作成したuseに対して、何らかの処理を行うことによって、
    当初の○と×の全組み合わせを調べることが可能になります。

再度硬貨の例の場合の実装コードを示しておきます。
```c++
// N = 3
// bit = 0, ..., 7
for (int bit=0; bit<(1<<N); bit++){
        // use = [0, 0, 0]で初期化
        vector<int> use(N,0);
        
        // 使用する部分を1に変更
        for (int j=0; j<N; j++){
            if (bit & (1<<j)) use[j]=1;
        }
        
        // ここまででuseが作成される
        // bit=0 : use=[0,0,0]
        // bit=1 : use=[0,0,1]
        // bit=2 : use=[0,1,0]
        // ...
        // bit=7 : use=[1,1,1]
    }
```
    

## 例題
それではbit全探索を用いて実際に問題を解いてみようと思います。
今回は[Atcoder](https://atcoder.jp/)の問題を利用させていただきたいと思います。

※ bit全探索の処理の流れをわかりやすくするため、全てをmain関数の中に書いたので、汚いのは悪しからず...(と思っていたけど1問目しかできてない。。)
※ マクロ等を極力使わずベタ書きするようにしましたが、使っていたらすみません。。

### 例題1(ABC167 C問題)
問題は[こちら](https://atcoder.jp/contests/abc167/tasks/abc167_c)から

問題の要約
> 学びたいアルゴリズムがM個ある。N冊の参考書があり、i番目の参考書の値段は$C_i$円、各i番目の参考書を読むことで、j番目のアルゴリズムの能力が$A_{ij}$だけ向上する。全てのアルゴリズムの能力をX以上にすることは可能か。また、可能なら必要な金額の最小値を求めよ。

<方針>
Nは12以下なので、全探索を行っても計算量は問題なさそう。従って、全探索で求める。
この時、N冊の参考書をそれぞれ使うか使わないかをbit全探索で求めてみる。


```c++
#include <iostream>
#include <vector>

using namespace std;

constexpr long long INF = 1LL << 60;

int main(){
    int N, M, X; cin >> N >> M >> X;
    vector<int> C(N, 0);
    vector<vector<int>> A(N, vector<int>(M, 0));

    // input
    for(int i=0; i<N; i++){
        cin >> C[i];
        for (int j=0; j<M; j++){
            cin >> A[i][j];
        }
    }

    // 最小値を求める問題なので、十分大きい値で初期化
    long long ans = INF;
    
    // bit全探索
    for (int bit=0; bit<(1<<N); bit++){
        vector<int> use(N, 0);
        for (int j=0; j<N; j++){
            if (bit & (1<<j)) use[j] = 1;
        }

        // 使用する参考書の全能力と金額の和を求める
        vector<int> wa(M, 0);
        long long price = 0;
        
        for (int i=0; i<N; i++){
            // 使用しない場合飛ばす
            if (use[i] == 0) continue;
            
            // 使用する場合
            price += C[i];
            for (int j=0; j<M; j++){
                wa[j] += A[i][j];
            }
        }

        // 全てがX以上か確認
        bool flag = true;
        for (int j=0; j<M; j++){
            if (wa[j] < X) flag = false;
        }

        // 全てX以上ならpriceを比較して更新
        if (flag) ans = min(price, ans);
    }

    // ansがINFのまま == X以上になるものがない
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}
```

### 例題2(ABC147 C問題)
問題は[こちら](https://atcoder.jp/contests/abc147/tasks/abc147_c)から

問題の要約
> N人の人がいる。N人はそれぞれ、必ず正しいことを言う「正直者」または真偽不明のことを言う「不親切な人」のいずれかです。人iは$A_i$個の発言をします。人iのj個目の発言は$x_{ij}, y_{ij}$で表され、$y_{ij}=1$の時は人$x_{ij}$は正直者という証言であり、$y_{ij}=0$の時は人$x_{ij}$は不親切な人という証言である。このN人の中に正直者は最大何人いるか。

<方針>
Nは15以下なので、正直者(1)or不親切な人(0)で全探索を行えば良い。
この時、bit全探索を用いて求めてみる

```c++
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>

using namespace std;

int N;

int solve(vector<map<int, int>> mp, vector<int> use){
    // 正直者: 1 不親切: 0
    for (int i=0; i<N; i++){
        if (use[i] == 0) continue;
        
        for (auto [xi, yi]: mp[i]){
            if (yi==1 && use[xi] == 0) return 0;
            if (yi==0 && use[xi] == 1) return 0;
        }
    }
    return accumulate(use.begin(), use.end(), 0);
}

int main(){
    cin >> N;
    vector<map<int, int>> mp(N);

    for (int i=0; i<N; i++){
        int Ai; cin >> Ai;
        for (int ai=0; ai<Ai; ai++){
            int xi, yi;
            cin >> xi >> yi;
            mp[ai][xi] = yi;
        }
    }

    int ans = 0;
    for (int bit=0; bit<(1<<N); bit++){
        vector<int> use(N,0); // 正直者
        for (int j=0; j<N; j++){
            if (bit & (1<<j)) use[j] = 1;
        }
        ans = max(ans, solve(mp, use));
    }
    cout << ans << endl;
}
```

# 参考文献
色々な本や動画を参考にしていますが、主に使用しているものを以下に載せておきます
1. [【bit全探索を理解する】AtCoder茶を目指す競プロ勉強会#3](https://www.youtube.com/watch?v=mEdFo-IbRdo)
1. [競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ ](https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E9%89%84%E5%89%87-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8A%9B%E3%81%A8%E6%80%9D%E8%80%83%E5%8A%9B%E3%82%92%E9%AB%98%E3%82%81%E3%82%8B77%E3%81%AE%E6%8A%80%E8%A1%93-Compass-Books%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%B1%B3%E7%94%B0/dp/483997750X)
1. [アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門](https://www.amazon.co.jp/%E6%9C%AC-AtCoder%E6%A0%AA%E5%BC%8F%E4%BC%9A%E7%A4%BE/s?rh=n%3A465392%2Cp_27%3AAtCoder%E6%A0%AA%E5%BC%8F%E4%BC%9A%E7%A4%BE)