AtCoderに向けて、アルゴリズムについて勉強を開始しました。
アルゴリズムの基礎は全探索ということで調べていたところ、bit全探索というものがあるらしいので学んだことをまとめようと思います。
解釈を間違ってる部分があれば遠慮なく教えてくださると助かります！
bit全探索とは
そもそも全探索とは、文字通り全パターンをしらみつぶしに調べていくみたいなイメージでしょう。
例えば数字の1～1000まで調べたかったらfor文とかをひたすら繰り返します。
一方、もしbool型の組み合わせではどうするのでしょうか？
例えばマルバツクイズに3人が参加してるとします。この時、回答の組み合わせを全探索するにはどうすればよいでしょうか。
調べたいのは{XXX}, {XXO}, {XOX}, {XOO}, {OXX}, {OXO}, {OOX}, {OOO}の8パターンですね。
これをどのようにプログラム上で探索するか、というのに使うのがbit全探索らしいです。
bit全探索の考え方
先ほど、3つのbool型の組み合わせは以下の8パターンと紹介しましたね。
{XXX}, {XXO}, {XOX}, {XOO}, {OXX}, {OXO}, {OOX}, {OOO}
これを0と1で表してみましょう。
000, 001, 010, 011, 100, 101, 110, 111
…この数字の並び、何か見覚えはありませんか？
これは2進数で0から7を順番に表示したものです！
例えば2進数が"011"なら、左からfalse、true、trueと解釈できます。
これを利用したらスムーズに全探索できそうですね。
bit全探索に必要に知識
先ほどの方法をプログラム上で実装するには2進数の演算が必要ですね。
プログラム上での2進数の計算を、「bit演算」 というようです。
今回は、bit全探索で用いるbit演算を見ていきましょう。
左シフト演算
まずはAPG4bにおける解説を見てみましょう。
ビット列を左向きにずらす操作を論理左シフト演算や単に左シフトといいます。
論理左シフト演算ではずらした後にはみ出た部分のビットは捨てられ、足りない部分のビットは0で埋められます。
例えば2進数の3、つまり0000 0011を左シフト演算したら、0000 0110となります。
文字通り左にシフトしただけですね。
これが計算的にどのような意味を持つかというと、2のi乗を意味します（iはシフトした回数）。
例えば 0000 0011（10進数の3）を4回シフトした 0011 0000 は10進数で48、つまり3*2^4ですね。
これをC++では、"<<"を用いて表します。
例えば、3を4回左シフトしたいなら (3 << 4) と表記します。
AND演算（論理積）
下の表で定義される演算をAND演算（または論理積）といいます。 このAND演算をビット毎に適用する演算をビット毎のAND演算（bitwise AND）といいます。
x y x AND y 0 0 0 0 1 0 1 0 0 1 1 1
どちらも1だったら1を返すって仕組みですね。
c++で実装するときは、"&"を用いて表します。
例えば5と14、つまり"1110"と"0101"の演算 (5 & 14) の解は"0100"、10進数の4ですね。
bit全探索の実装方法
さて、長くなってしまいましたがここからが本題です。
c++でbit全探索する方法について紹介していきます。
まずは以下のコードをご覧ください。
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
for (int bit = 0; bit < (1<<N); bit++) {
for (int i=0; i<N; i++) {
if (bit & (1<<i)) cout << "o ";
else cout << "x ";
}
cout << endl;
}
}
これは数字を入力すると、その個数での組み合わせをoとxで表現するプログラムです。
例えば「3」を入力すると、次のように返ってきます。
x x x
o x x
x o x
o o x
x x o
o x o
x o o
o o o
ちゃんと全パターン表示できていますね。
それではコードの中身を順番に見ていきます。
コードの解説
for (int bit = 0; bit < (1<<N); bit++) {
この部分がbit全探索の要の部分です。
変数bitの値を1ずつ増やしてるだけですが、これが2進数的にはすべての0と1の組み合わせを試してることになるんですね。
終了条件の bit < (1<<N) が少しわかりづらいでしょうか。
上で解説したとおり、 (1<<N) というのは "2^N" を表しています。
例えば、N=3なら2^Nは8、つまり"1000"であり、このfor文ではそれ未満の"0000"～"0111"まで探索できます。
for (int i=0; i<N; i++) {
if (bit & (1<<i)) cout << "o ";
else cout << "x ";
}
変数 i は1ずつ増えていく変数です。
そして、2行目では i を( 1<<i )、つまり左シフト演算の回数として使っています。
つまり、 ( 1<<i ) は"0000", "0001", "0010", "0100"… のように変化します。
これを&（AND演算子）によって論理和を取ったらどうなるでしょう。
例えば、変数bitの値が"1010"だとします。
| 変数i | (1<<i) | 変数bit | bit & (1<<i) | if (bit & (1<<i)) |
|---|---|---|---|---|
| 0 | 0001 | 1010 | 0000 | false |
| 1 | 0010 | 1010 | 0010 | true |
| 2 | 0100 | 1010 | 0000 | false |
| 3 | 1000 | 1010 | 1000 | true |
上の表からわかる通り、 bit & (1<<i) というのは (i+1) 桁目が0なら0、1なら0以外の数を返します。
そして、実はif文というのは0ならfalse、それ以外の数ならtrueだと判断します。
つまりこのif文は、 (i+1) 桁目が0ならfalse、1ならtrueとなるのです。
あとは true のときに実行したい文・false の時の実行したい文をそれぞれ書けば完了です！
AtCoder の例題
以下の問題を解いてみました。
AtCoder Beginner Contest 128 C - Switches
問題の概要を説明すると、以下のような感じです。
- オンオフスイッチがN個、電球がM個ある
- スイッチと電球はそれぞれ繋がっていて、どれに繋がってるかの情報が与えられる
- 電球には、「繋がっているスイッチが偶数個オンになると点灯する電球」・「奇数個オンになると点灯する電球」の2種類がある。それぞれの電球がどちらなのかの情報も与えられる
- 電球が全て点灯するスイッチの組み合わせは、全部で何パターンあるか
ここまでの知識があれば十分解ける問題になっています。
先ほどのコードを書き換えながら解いてみましょう！
解説
スイッチがたくさんあり、そのパターンごとにどうなるかを調べる問題です。
オンとオフのスイッチの組み合わせと聞くと、bit全探索が使えそうですよね。
さて、無事解けましたでしょうか。
綺麗なコードではないかもしれませんが、私の回答を載せておきます。
#include <bits/stdc++.h>
using namespace std;
//ビット全探索の練習問題
int main(){
int N, M;
cin >> N >> M;
//各電球が、どのスイッチと繋がってるのかを取得
vector<vector<int>> s(M);
for(int i=0; i<M; i++){
int k;
cin >> k;
for(int j=0; j<k; j++){
int num;
cin >> num;
s[i].push_back(num);
}
}
//各電球が、偶数で点くのか奇数で点くのかを取得
vector<int> k(M);
for(int i=0; i<M; i++){
cin >> k[i];
}
//ここからビット全探索
int ans = 0;
//「あるスイッチのパターンにおいて、」
for (int bit = 0; bit < (1<<N); bit++) {
int light = 0;
//「ある電球と」
for(int i=0; i<M; i++){
int count = 0;
//「繋がってるスイッチが、」
for (int x : s[i]) {
//「オンであるかを調べる」
if (bit & (1<<x-1)) {
count++;
}
}
//スイッチのオンの数が偶数or奇数によって、点灯するかが決まる
if(count % 2 == k[i]){
light++;
}
}
//点灯数と電球の数が同じ、つまり全て点灯なら答えのパターンの1つである
if(light == M){
ans++;
}
}
cout << ans << endl;
}
上半分は、与えられる情報を取得してるだけですね。
二次元配列 s には電球がどのスイッチと繋がってるかの情報、配列 k には電球が点灯するのは奇数か偶数かの情報を保存しています。
for (int bit = 0; bit < (1<<N); bit++) {
↑ここがbit全探索の、2進数を1ずつ増やしてる部分ですね。
for(int i=0; i<M; i++){
↑こちらは、特定の電球について1つずつ調べるために変数 i を増やしています。
for (int x : s[i]) {
//「オンであるかを調べる」
if (bit & (1<<x-1)) {
count++;
}
}
//スイッチのオンの数が偶数or奇数によって、点灯するかが決まる
if(count % 2 == k[i]){
light++;
}
for (int x : s[i]) の部分は、先ほどのコードでは"0001", "0010", "0100"… と増やしてた部分です。
今回はすべてのスイッチを調べる必要がなく、ある電球に繋がっているスイッチのみを調べればよいです。
そのため、配列 s[i] に入ってる値だけを調べればいいんですね。
あとはスイッチがオンだったら count++ して、ループが終わったらすべてのスイッチのオンの数 count が奇数or偶数なのかを調べます。
そしたらその電球が点灯しているので light++ して、最終的に点灯している電球の数 light が全ての電球だったら答え ans を1増やします。
まとめ
いかがだったでしょうか。
bit全探索について自分で学習してみて、分かりづらく感じた場所を重点的に解説してみました。
次は順列全探索を勉強してみようかなと思っています。
「今回の内容が、マルバツではなく数字になったもの」くらいの認識なのですがどうなのでしょうか…笑
参考文献
勉強の際、以下の記事を参考にしました。
大変参考になりました！ありがとうございます。
↓ bit全探索について分かりやすくまとめているページです。
↓ bit演算全般について、幅広くまとめられているページです。