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;
return 0;
}この記事では、bit全探索について解説します。
Python で解説した記事もあります。
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つのボールについて「選ぶ」と「選ばない」の2通りの選び方があります。
赤のボールについて2通り、青のボールについて2通り、黄のボールについて2通りなので、全体の選び方としては「2*2*2＝8通り」→「23=8」となります。
4つのボールだと「2*2*2*2＝16通り」→「24=16」の選び方があります。「0000」から「1111」までを試せば、すべての選び方を列挙できます。
５つの場合は「2*2*2*2*2＝32通り」→「25=32」。「00000」から「11111」までを試せばいいです。
N個の場合は「2N通り」の選び方があります。N桁の2進数を使うことですべての組み合わせを試すことができます。
N個の中から選ぶ選び方は、２N通り
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つの中から選ぶときを考えてみます。
４つの中から選ぶ場合は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;
return 0;
}まとめ
bit全探索を使えば、「選ぶ」「選ばない」のような2種類の選択する探索が簡単にできます。
N個の中からいくつか選ぶときの選び方は、2N通りあります。
選ばないを「0」、選ぶを「1」で考えれば、2進数ですべての選び方を列挙することができます。
「1 << N」は、1をNだけ左にシフトします。これを使えば『for (int i = 0; i < (1 << N); i++)』ですべての選び方について探索できます。
N個の中のj番目が選ばれているか（「1」なのか）を判定するにはAND演算子を使います。
