zukabit全探索探索を実装するよ。
本記事では，bit全探索の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。
本記事の概要
まずは，bit全探索のお気持ちをお伝えしていきます。その次に，二分探索の雛形となる実装をお伝えしていきます。
bit全探索のお気持ち
実装の雛形
お気持ち
bit全探索は，ある$N$個の事象の0or1を全て数え上げるために利用される方法です。例えば，以下のような例題を考えてみましょう。
$N$ 個の正の整数 $x_{0}, x_{1}, \ldots, x_{N-1}$ と、正の整数 $Y$ とが与えられます。$x_{0}, x_{1}, \ldots, x_{N-1}$ の中から何個か選んで総和を $Y$ とできるような整数の組み合わせの総数を求めてください。ただし，$1 \leq N \leq 20$とします。
まさに，この例題は$N$個の整数が選ばれる（=1）場合と選ばれない（=0）場合を全て考えるような問題です。選ばれるor選ばれないをbitで考えていく方法がbit全探索です。ただし，計算量は$O(2^N)$となるため，$N$が小さい場合でないと利用できない方法になっています。
zukaある数字を2進数で考えた時に各bitは0か1しか取らないよね。その性質を利用してforループの変数を$0$から$2^N-1$まで考えて各bitの0or1を抽出していくことで，$2^N$通りの組み合わせを全て列挙できる優れものなんだ。
雛形
実際に先ほどの例題を解いていきましょう。最初に，入力例を示しておきます。
入力例
$N$ $Y$
$x_1$ $x_2$ $\ldots$ $x_{N-1}$
実装例
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
int N;
int Y;
cin >> N >> Y;
int X[N];
rep(i, N) cin >> X[i];
// bitsが0から2^Nまで動く
// bitsのn番目のbitがx_nが選ばれるかどうかに対応している
rep(bits, 1<<N){
// x_nが選ばれるかどうかのフラグ
bool flag[N];
// bitsの各bitをみていく
rep(n, N){
// この部分でbitsの各bitを&で抽出している
// 1の場合はtrueを0の場合はfalseを入れる
if (bits & (1<<n)) flag[n] = true;
else flag[n] = false;
}
// ここからソルバー
int ans = 0;
int sums = 0;
// 選ばれないx_nにはflag[n]がfalse(=0)になっているはずなのでかけ算して相殺する
rep(i, N) sums += X[i] * flag[i];
if (sums == Y) ans ++;
}
cout << ans << endl;
}考えついた人はすごいよね。確かに「選ぶ・選ばない」の0or1の世界とbitの世界は似ているものがある。でもそこに気づくのって案外難しいと思うよ。
コメント