bit全探索について

magnifying-glass-gfea プログラミング

N個の要素の中からいくつかを選ぶような問題は、bit全探索を使えば簡単に実装できます。

次のような問題を考えてみましょう。

A1,A2,・・・ANのN個の整数が与えられます。 これらの整数からいくつかを選んで、その総和がKとなるような選び方が存在するかを求めてください。

以下のコードは、bit全探索を使った解法です。

#include <bits/stdc++.h>
using namespace std;

int main () {
  // 入力
  int N, K;
  cin >> N >> K;
  
  int A[N];
  for (int i = 0; i < N; i++) cin >> A[i];

  bool isOK = false;

  // すべての選び方を試して、総和がKになるものがあるかを調べる
  for (int i = 0; i < (1 << N); i++) {

    int sum = 0;
    
     // N個の中からビット列の「1」のところの整数が選ばれているとして総和を求める   	
    for (int j = 0; j < N; j++) {
      
      // 選ばれているとき
      if (i & (1 << j)) sum += A[j];
    }
    
    // 総和がKだったとき
    if (sum == K) isOK = true;
  }

  // 出力
  if (isOK) cout << "Yes" << endl;
  else cout << "No" << endl;
}

この記事では、bit全探索について解説します。

2進数とは

bit全探索では、2進数の考え方を使います。

2進数とは何でしょうか?

2進数は、「0」と「1」の2つの数字を使って数を表現します。

コンピュータは、情報を電気信号の「ON」と「OFF」の2つの状態で管理しています。そのため、コンピュータ内部では、「0」と「1」の2つの数字で表現する2進数で情報を扱っています。

私たちが普段使っているのは10進数で、0から9までの数字を使って数を表します。一番大きい数の「9」の次は桁があがって「10」になります。

2進数も同じように、一番大きい数の「1」の次は桁が上がって「10」になります。

10進数の数に対応する2進数は以下のようになります。

左が10進数の数で、それを2進数で表したのが右です。

  • 0:0
  • 1:1
  • 2:10
  • 3:11
  • 4:100
  • 5:101
  • 6:110
  • 7:111
  • 8:1000

bit全探索の考え方

2進数の「0」と「1」を使って、すべてのパターンを探索する方法がbit全探索です。

例えば、「赤」「青」「黄」の色がついた3つボールから、いくつか選ぶときの組み合わせは、以下のような8通りです。

  • 赤 青 黄
  • 赤 青  
  • 赤   黄
  • 赤    
  •   青 黄
  •   青  
  •     黄
  • どれも選ばない

ボールを選んだときを「1」、選ばないときを「0」とすれば次のようになります。

  • 赤 青 黄:1 1 1
  • 赤 青  :1 1 0
  • 赤   黄:1 0 1
  • 赤    :1 0 0
  •   青 黄:0 1 1
  •   青  :0 1 0
  •     黄:0 0 1
  •      :0 0 0

1つのボールについて「選ぶ」と「選ばない」の2通りの選び方があります。

赤のボールについて2通り、青のボールについて2通り、黄のボールについて2通りなので、全体の選び方としては「2*2*2=8通り」→「23=8」となります。

4つのボールだと「2*2*2*2=16通り」→「24=16」の選び方があります。「0000」から「1111」までを試せば、すべての選び方を列挙できます。

5つの場合は「2*2*2*2*2=32通り」→「25=32」。「00000」から「11111」までを試せばいいです。

N個の場合は「2N通り」の選び方があります。N桁の2進数を使うことですべての組み合わせを試すことができます。

N個の中から選ぶ選び方は、2N通り

2進数で必要な数までループさせる

3つの中から選ぶ選び方は8通りでした。2進数で「000」から「111」まで列挙できれば全探索できます。「000」は10進数で「0」、「111」は10進数で「7」です。

以下のコードを実行すれば、0から7まで出力します。

#include <bits/stdc++.h>
using namespace std;
 
int main() {

  for (int i = 0; i < (1 << 3); i++) {
    cout << i << endl;
  }

  return 0;
}

/*
実行結果
0
1
2
3
4
5
6
7
*/

6行目の「(1 << 3)」は、1を3つだけ左にシフトします。

左シフト

「<<」は左シフトです。「(1 << N)」は、1をNだけ左にシフトします。足りない部分は「0」で埋められます。

  • 1を1つだけ左にシフト:10
  • 1を2つだけ左にシフト:100
  • 1を3つだけ左にシフト:1000
  • 1を4つだけ左にシフト:10000

Nはこの場合「3」なので、1を3つだけ左にシフトしています。つまり、「(1 << 3)」は「1000」のことで、10進数では「8」になります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {

  cout << (1 << 3); // => 8
  
  return 0;
}

次のコードのfor文は、どちらも「0」から「7」まで出力します。

for (int i = 0; i < 8; i++) {
  cout << i << endl;
}

// 上のfor文と同じで「0」から「7」まで出力する
for (int i = 0; i < (1 << 3); i++) {
  cout << i << endl;
}

次に4つの中から選ぶときを考えてみます。

4つの中から選ぶ場合は16通りで、「0000」から「1111」までが必要です。「1111」は、10進数で「15」です。

以下のコードを実行すれば「0」から「15」まで出力します。

#include <bits/stdc++.h>
using namespace std;
 
int main() {

  for (int i = 0; i < (1 << 4); i++) {
    cout << i << endl;
  }

  return 0;
}

つまり、N個の中からの選び方は『for (int i = 0; i < (1 << N); i++)』を使えばいいということになります。

N個の中からの選び方を列挙するには、次のように書きます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;

  // 0から2のN乗までのすべての選び方を試す
  for (int i = 0; i < (1 << N); i++) {
    
  }

  return 0;
}

どれが選ばれているかを判定する

『for (int i = 0; i < (1 << N); i++)』を使うことで、必要な選び方について試すことができるようになりました。

3個の中から選ぶときは、「000」から「111」までです。

次に必要なのは、3個の中でどれが選ばれているのか(「1」になっているか)を判定する方法です。

以下のコードは、「011」の各桁について「1」かどうか判定します。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int bit = 3; // => 011

  // 1桁ずつ判定
  for (int j = 0; j < 3; j++) {
    
    // 1か判定
    if (bit & (1 << j)) {
      cout << j << " : 1です" << endl;
    } else {
      cout << j << " : 0です" << endl;
    }
  }

  return 0;
}

/*
実行結果
0 : 1です
1 : 1です
2 : 0です
*/

11行目の『if (bit & (1 << j))』で対象の桁が「1」かどうか判定しています。

「(1 << j)」は左シフトです。j=1だと「(1 << j)」は「10」になります。

j=1で考えると、『if (bit & (1 << j))』は、bit=011なので「if (011 & 010)」になります。

AND演算子

『if (bit & (1 << j))』の「&」はAND演算子です。

AND演算は、各ビットについて両方が「1」のときに「1」になります。

つまり「011 & 010」は「010」になります。

  011
& 010
-----
= 010

「if (011 & 010)」は、「if (010)」ということです。

C++のif文は「0」はFalseになり、「非0」はTrueになるので、「if (010)」は、Trueになります。

2進数「010」は、10進数で「2」です。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  if(0) cout << "0はTrueです" << endl; // => 0なので実行されない
  if(1) cout << "1はTrueです" << endl;
  if(2) cout << "2はTrueです" << endl;

  return 0;
}

/*
実行結果
1はTrueです
2はTrueです
*/

j=2だと、『if (bit & (1 << j))』は「if (011 & 100)」→「if (000)」なのでFalseになります。

if (bit & (1 << j))で、bitのjビット目が「1」か判定できる。

bit全探索

以下コードが、bit全探索の基本的な書き方です。

// 0から2のN乗までのすべての選び方を試す
for (int i = 0; i < (1 << N); i++) {

  // N個について0個目からN個目まで1つずつ確認
  for (int j = 0; j < N; j++) {
      
    // 選ばれているとき
    if (i & (1 << j)) {
    }
  }
}

3つのボールからいくつか選ぶときの組み合わせは、以下のようなコードを書けばすべて列挙できます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N = 3;
  string A[3] = {"赤", "青", "黄"};

  // 0から2のN乗までのすべての選び方を試す
  for (int i = 0; i < (1 << N); i++) {
    // N個の中でどれが選ばれているか
    for (int j = 0; j < N; j++) {
      
      // 選ばれているとき
      if (i & (1 << j)) {
        cout << A[j] << ' ';
      }
    }
    
    cout << endl;
  }

  return 0;
}

/*
実行結果
赤 
青 
赤 青 
黄 
赤 黄 
青 黄 
赤 青 黄 
*/

一番初めの問題をもう一度見てみましょう。何をしているのかわかるようになったのではないでしょうか?

A1,A2,・・・ANのN個の整数が与えられます。 これらの整数からいくつかを選んで、その総和がKとなるような選び方が存在するかを求めてください。

#include <bits/stdc++.h>
using namespace std;

int main () {
  // 入力
  int N, K;
  cin >> N >> K;
  
  int A[N];
  for (int i = 0; i < N; i++) cin >> A[i];

  bool isOK = false;

  // すべての選び方を試して、総和がKになるものがあるかを調べる
  for (int i = 0; i < (1 << N); i++) {

    int sum = 0;
    
     // N個の中からビット列の「1」のところの整数が選ばれているとして総和を求める   	
    for (int j = 0; j < N; j++) {
      
      // 選ばれているとき
      if (i & (1 << j)) sum += A[j];
    }
    
    // 総和がKだったとき
    if (sum == K) isOK = true;
  }

  // 出力
  if (isOK) cout << "Yes" << endl;
  else cout << "No" << endl;
}

まとめ

bit全探索を使えば、「選ぶ」「選ばない」のような2種類の選択する探索が簡単にできます。

N個の中からいくつか選ぶときの選び方は、2N通りあります。

選ばないを「0」、選ぶを「1」で考えれば、2進数ですべての選び方を列挙することができます。

「1 << N」は、1をNだけ左にシフトします。これを使えば『for (int i = 0; i < (1 << N); i++)』ですべての選び方について探索できます。

N個の中のj番目が選ばれているか(「1」なのか)を判定するにはAND演算子を使います。

参考

AC – 3.05.ビット演算 – AtCoder

bit全探索 – けんちょんの競プロ精進記録

C++のfalseは0でtrueは非0だと思い込んでいた話 – PCの歯車

タイトルとURLをコピーしました