こんにちはへきぼこです
S高等学校の2年生です
今回は競プロで使うテクニックであるbit全探索について解説していきます
bit全探索のイメージを皆さんに知っていただこうと思います
コードはC++で書いていきます
bit全探索って何？
bit全探索とはbit演算を使って
N個の中からいくつか選ぶ方法をすべて列挙するものです
どういうときに使うか？
例えば３色の赤、青、緑のボールがあってそこからいくつか選ぶ方法を列挙していきましょう
こんな感じに全部で８通りを列挙できました
全てを列挙する方法は$2^N$通りあります
なぜbit全探索を使うか？
これをプログラミングでやるとどうなるでしょうか
まず数値で扱いやすいようにするため、0を選ばない、1を選ぶとしましょう
forループを重ねる方法でやるとこうなります
#include <bits/stdc++.h>
using namespace std;
int main() {
cout<<"全列挙"<<endl;
int cut=0;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++){
if(i==1){
cout<<"赤 ";
}
if(j==1){
cout<<"青 ";
}
if(k==1){
cout<<"緑 ";
}
//endlは改行
cout<<endl;
cut++;
}
}
}
cout<<cut<<"通り"<<endl;
}
全列挙
緑
青
青 緑
赤
赤 緑
赤 青
赤 青 緑
//何も選ばないも合わせて
8通り
N=3ならまだできますがN=20とかになると、この方法では実装に途方もない時間がかかります
i,j,kはそれぞれの色を選ぶか選ばないかを表しています
ここでj,j,kを並べてみましょう、そして二進数としてみると
全ての値が被らずに0から7まであります。
また、0が選ぶ、1が選ばないを表しているので、二進数の桁を見ればボールを選んでいるかわかります
という事は0~7のforを行えばよさそうです
bit全探索の実装
ここから(1<<N)というものが出てくると思います
(a<<b)は二進数で見たときにaをb桁ずらして0をいれるというものです
(101<<3)=101000こんな感じです
つまり(1<<N)は二進数で見たときに1をN桁にするというものですが一番最初が0桁目になります
// (1<<3)は二進数で見たときに３番目の桁を1にするという事1000(2)=8
for(int i=0;i<(1<<3);i++){
}
このforの中身に二進数の値からどのボールを選んでいるかの復元をしていきます
5だったらこうなります
配列でどのボールかを保存しておきます
1桁目が1だったら緑を選んでいる、2桁目だったら青、3桁目だったら赤という感じです。
vector<string>S={"緑","青","赤"};
// (1<<3)は二進数で見たときに３番目の桁を1にするという事1000(2)=8
for(int i=0;i<(1<<3);i++){
for(int d=0;d<3;d++){
//iのd桁目が１になっているか調べる
if(i & (1<<d)){
cout<<S[d]<<" ";
}
}
cout<<endl;
}
実行すると
緑
青
緑 青
赤
緑 赤
青 赤
緑 青 赤
８通りになりました！
終わり
いかがでしたでしょうか
bit全探索はいろんな工夫ができる楽しいテクニックです
bit全探索はAtCoderのC問題でたまに出てくるので解けるかもしれません
例題を置いときます
ABC374 C
https://atcoder.jp/contests/abc374/tasks/abc374_c
ABC289 C
https://atcoder.jp/contests/abc289/tasks/abc289_c
ABC384 C
https://atcoder.jp/contests/abc384/tasks/abc384_c
模範解答（といえるかわからないけど）解法と一緒に書いておきました
ABC374 C
https://atcoder.jp/contests/abc374/submissions/71270040
ABC289 C
https://atcoder.jp/contests/abc289/submissions/71269699
ABC384 C
https://atcoder.jp/contests/abc384/submissions/71270419
bit全探索の応用もbitDPやK進数全探索などいろいろあるのでそれも調べてみるといいですね