※以後、ABCといったらAtCoder Beginner Contestのことを指す。
※この記事に付け足してほしいことがあったらその都度教えてください。
ABC356-Cにbit全探索が出た。
ABC358-Cにbit全探索が出た。
ABCの昔の解説記事を書こうとしたら、ABC002-Dがbit全探索だった。
ということなので（どういうことなので？）、この記事ではbit全探索についてまとめる。
bit全探索の概要
まず、bitについてさっぱりな人はこの記事を見よう。
bitは2進法のため、主に全探索をするときに2パターンの在り方があるときに使える。
例えば、
・物を買う、買わない
・グループに参加する、参加しない
という2つ選択肢があったとする。そんなときに使うものだ。
例えば、物の買う買わないについては
・i桁目が0ならi番目のものを買わない。
・i桁目が1ならi番目のものを買う。
がある。また、グループについては
・i桁目が0ならi番目の人は参加しない。
・i桁目が1ならi番目の人は参加する。
こんな感じ。
bit全探索の考え方
bit全探索は、$0$~$2^{桁数}-1$までを全探索すれば全列挙ができるよねという考えに基づいている。
例えば3桁を考えるときは、
| 0桁目 | 1桁目 | 2桁目 | sum |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 2 |
| 1 | 1 | 0 | 3 |
| 0 | 0 | 1 | 4 |
| 1 | 0 | 1 | 5 |
| 0 | 1 | 1 | 6 |
| 1 | 1 | 1 | 7 |
まあsumが$0$~$7=2^3-1$のとき全部列挙で来てるからいいよね。
桁数がそれこそ星の数こそあったらドカンだが、高々20くらいだったら1秒以内に全列挙できる。
bit全探索の実装
まず、C++にはbitsetという機能がある。この機能を使えば任意の整数を2進法に直した配列が出来上がる。
これをもとにしてi桁目が0ならしない、1ならするという感じのができる。
たとえば、こんな問題があったとしよう。
部分和問題
$N$個の整数$A_0,A_1...A_{N-1}$がある。
この中からいくつか選び、その総和が$X$になるようなものは存在するか。
作れるならYes、作れないならNoと出力せよ。
制約
$1\leq N \leq20$
$1\leq A,X\leq 5*10^7$
この問題は再帰関数を学ぶ時に見たことがないだろうか。
これをbit全探索で解くと、次のようになる。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,x;cin>>n>>x;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<(1<<n);i++){
bitset<20> bit(i);
int sum=0;
for(int j=0;j<n;j++)
if(bit[j])sum+=a[j];
if(sum==x){
cout<<"Yes\n";
return 0;
}
}
cout<<"No\n";
}
さて、ここで(1<<N)とはどういう意味が気になった人もいるのではなかろうか。
<<は、左シフト演算という計算である。
例えば、
・(5<<2)=$5*2^2$=20
・(1<<10)=$1*2^{10}$=1024
こんな感じだ。
この機能を使ってfor文を回すことで、$0$~$2^N-1$のiを作れる。
基本的には、
・A[0]は$2^0$の位
・A[2]は$2^2$の位
・A[N-1]は$2^{N-1}$の位
を表している。
注意点
bit全探索を使うにあたっての注意点を説明する。
bitsetの<>
bitset<>のなかは、絶対に定数しか置けない。
bitset<>に変数Nを入れるとバグが発生する。
この事実を知らないとなかなか気づけないと思うので、そこは覚えておこう。
実行時間
たとえば、上記の部分和問題だと、iを$2^N$回、jを$N$回まわしているので、実行時間が$O(2^NN)$かかる。もしこの問題の制約が$N\leq30$だとTLEしてしまう。
例えば、この問題をbit全探索で解こうとすると、実行時間が$O(2^MMN)$かかるので、どうあがいてもTLEする。
bit全探索を使うときは、Nのとりえる大きさに注意しよう。
まとめ
ABC301~ABC363のCDにおいて、bit全探索が出たのは高々3回しかない。しかし、その3問は全てdiff600以下だ。緑コーダーを目指す人は絶対に落とせない。さらに、水コーダーを目指す人にとっては、のちのbitdpの学習においてもbitの考え方は継承する。完璧に理解しておかなければならない壁の一つがbit全探索だ。
おまけ・bit全探索まとめ（随時更新）
ABC002-D 派閥 試験管 diff1418
ABC356-C Keys diff273
ABC358-C Popcorn diff568