【c++で楽しく実装!】bit全探索

zuka

bit全探索探索を実装するよ。

本記事では,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は01しか取らないよね。その性質を利用して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;
}
zuka

考えついた人はすごいよね。確かに「選ぶ・選ばない」の0or1の世界とbitの世界は似ているものがある。でもそこに気づくのって案外難しいと思うよ。

よかったらシェアしてね!

コメント

コメントする

目次
閉じる