bit全探索練習　備忘録

bit全探索の練習備忘録として。

【参考】
https://qiita.com/Noiri/items/ea5009b3e7bdf816ef88#5-bit%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%82%92%E5%AE%9F%E8%A3%85%E3%81%99%E3%82%8B
https://drken1215.hatenablog.com/entry/2019/12/14/171657


```php
//bit探索の基本ループ
    for(int bit=0;bit<=(1<<n);bit++){
     //0と1の組み合わせが2^nある場合、bitを2^n分ループさせる。
        for(int i=1;i<n;i++){
            if(bit & (1<<i)){
             //bitのi桁目が1の時だけこの中身を実行する
            }
        }
    }
```

AtCoder Regular Contest 061C
C - たくさんの数式
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1112433/5919fa35-1f35-82d0-65f0-e14e3bd8462e.png)

数字の間を'+'を入れる組み合わせをすべて計算して足し合わせる問題。
文字数がNだとすると、文字の間はN-1個なので、これをtとする。
1<<t == 2^tだけ組み合わせがあるのはすぐわかる。
bit探索っぽいのは気づくので、どう実装するか。
ある組み合わせの時の計算値をsum、全sumの合計値をansとする。（ansは答えそのもの）
sumの計算過程での変数をaとする。

※知識※
数字文字列-'0'で、数字型に変換できる！ちょうべんり。

・ある組み合わせをbitとする。探索範囲は先の通り、1<<tまで。
・一番上の桁をaに代入　
・一つずつbitｼﾌﾄして、1or0を検索。文字の間だけ探索なのでtまで。
　1を+ありとする。
・検索は下の桁からになるけど、結局対称性あるので、どっちから数えても一緒。
・bitのj桁が1だったら'+'入るのでa=0にリセット。
・次の数として、S.at(j+1)をaに代入して、もう一度探索。
・bitのj桁が0だったら、if分飛ばして次へ。aが0じゃない値が残るので、
　×10して、次の桁を足す。

2456って文字列で、bit=2=010って状態を考える。
t=3 (4文字-1)
a=S.at(0)=2 (頭の文字)

j=0
1<<0 & 010 ⇒F (bitの1桁目は0なので)
a=10*2+S.at(0+1)=24

j=1
1<<1 & 010 ⇒T (bitの2桁目は1)
sum=0+24=24
a=0
a=10*0+S.at(1+1)=5

j=2
1<<2 & 010 ⇒F
a=10*5+S.at(2+1)=56
ループ終わって
sum=24+56=80
ans=0+80=80
これが繰り返し

ゆっくり読めば理解できたが、考え付くのは難しい。
慣れですね。

```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

//https://drken1215.hatenablog.com/entry/2019/12/14/171657

int main(void){
    string S;
    cin>>S;
    int t=S.size()-1;
    long long ans=0;
    for(int bit=0;bit<(1<<t);bit++){//組み合わせの数
        long long sum=0;
        long long a=S.at(0)-'0';//一番上の桁から数える。-'0'でcharから数字へ変換
        for(int j=0;j<t;j++){//各要素の数 
            if((1<<j) & bit){//bitのj桁が1だったら
                sum=sum+a;
                a=0;//次の数作りのためリセット
            }
            a=10*a+S.at(j+1)-'0';//aを桁上げして、次の数を足す
        }
        sum=sum+a;
        ans=ans+sum;
    }
    cout<<ans<<endl;
}
```

AtCoder Beginner Contest 128
C - Switches

https://atcoder.jp/contests/abc128/tasks/abc128_c
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1112433/f0d49894-d95e-ca12-a4c8-c3ae43b37aac.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1112433/f818ecc9-993b-e96f-2f7d-e0dd7a19d26f.png)

SWのON/OFFパターンは2^Nとすぐわかる。
N~10なので、全探索できるなと判断してbit探索に舵を切る流れ。
複雑だけど丁寧に入力、処理しけばやることはシンプル。

SW:5個だとすると、
00000~11111までの2^5分の探索をかける。
00110みたいな時は、SW:2,3だけON。
この時各電球は点灯条件を満たすか？　という感じで実装。
1個でもNGだったらそこでBreakでおｋ。
NGでなかったケースをカウントしていけば、条件を満たす組み合わせ数になる。


```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;

int main(void){
    int N,M;//N:ｽｲｯﾁの数　M:電球の数
    int k[20];//電球iにつながるｽｲｯﾁの数がk[i]
    int s[20][20];//k[i]につながるｽｲｯﾁがs[j]
    int p[20];//p[i]=0は偶数個、p[i]=1は奇数個　ｽｲｯﾁONでiが点灯
    int ans=0;
    cin>>N>>M;

    for(int i=0;i<M;i++){
        cin>>k[i];
        for(int j=0;j<k[i];j++){
            cin>>s[i][j];
        }
    }
    for(int i=0;i<M;i++){
        cin>>p[i];
    }
    //SWの数はN個なので、点灯の組み合わせは2^N通り。
    //2^N通りをbit全探索、その時々の状態が全点灯か否かを判定する
    //条件は全点灯なので、1個でも点灯しないのがあったらbreakする
    for(int i=0;i<(1<<N);i++){//bit=i 2^N通りループ
        int ng_flg=0;
        for(int j=0;j<M;j++){//電球jのSW ON数を数えるループ
            int sw_count=0;
            for(int l=0;l<k[j];l++){//電球についたｽｲｯﾁ1つ1つを判定
                if(i & (1 << (s[j][l]-1))){//SWのON状態判定 SW名は1～なので、1を引く
                    sw_count++;//SW ONの数をカウント
                }
            }
            if(sw_count%2!=p[j]){//電球jのSW ON数の適合判定
                ng_flg=1;
                break;//一個でも点灯しない電球あったらＮＧ判定
            }
        }
        if(ng_flg==0){//全電球を調べて、NGフラグ立ってない=全点灯
                ans++;//bit=iは全点灯する組み合わせなので、ansをカウント
        } 
    }
        cout<<ans<<endl;
}
```

ABC197_C
https://atcoder.jp/contests/abc197/tasks/abc197_c
数列Aに対し任意の1つ以上の組でOR⇒XOR演算し、最小値を出す問題。
数列Aの間いずれかに切れ目を入れるか入れないか、というポイントをbit探索する。
OR演算子として、
a |= b　でa= a OR bのビット演算。
011 OR 101 =111 (両方一致で0になる)
a ^= b　でb= a XOR bのビット演算。
011 XOR 101 =110 (両方一致で0になる)

n個の間の数分なので、探索は2^n-1になる。
以下bit内の1ﾙｰﾌﾟ
・各探索の最初はA[0]なので、OR=A[0]とする
・XOR=0と初期化する。
・分割が入るまで（bitのi-1桁目が1になるまで）ない時はOR積算をする。
・分割が入ったら、それまでのORでXORをとる
・最後にXORをとって、1つのbit数でのループが完了。

Aはでかいけど、nは20なので2^19（1e6以下）程度。
nループは20までなのでまぁいけそうな感じ、と判断できる。



```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin>>n;
    ll A[n+100];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    ll OR =0;
    ll XOR=0;
    ll ans=1e15;

    for(int bit=0;bit<=(1<<n-1);bit++){
        OR =A[0];
        XOR =0;
        for(int i=1;i<n;i++){
            if(bit & (1<<(i-1))){
                XOR^=OR;
                OR=0;

            }
            OR|=A[i];
        }
        XOR^=OR;
        ans=min(ans,XOR);
        //a|=b OR
        //a^=b XOR
    }
    cout<<ans<<endl;

}
```