bit全探索をゆるくマスター

fami

2024年11月30日 18:44

競技プログラミングをやっているとC問題で出てくる【bit全探索】。「bitが出てきて分からなくなる。」「コードを読んでも何をしているのかよくわからない。」といった声が出てくるアルゴリズムだと思います。

そんな比較的習得が難しいbit全探索ですが、できるようになると非常に良いです。気持ちがいいです。なので頑張って取得しましょう。

Ⅰ：bit全探索とは

まず”全探索”についてですが、これは考えられるパターンを全て列挙することです。下の例を考えてみましょう。

3つの数字が書かれたカード１，２，３があります。
この中から好きな枚数のカードを選んで足します。
この時、考えられる和を列挙してください。

列挙するときには、まず１枚選ぶか、２枚選ぶか、そもそも選ばないか、、といった選ぶ枚数を考えて、そのあと選ぶカードを考えると全て列挙できそうですね。（下の図）

では、プログラミングで選んだとか選ばなかったとかを管理する必要があります。↑の図のように「白＝選んだ」「黒＝選ばない」だとプログラミングで表現するのは大変なので、もっと簡単に「１＝選んだ」「０＝選ばない」としましょう。２進数です。

これがbit全探索です。どのカードを選んだか/選んでいないかを２進数（０と１）で管理する方法です。名前についている”bit”はこの２進数を表しています。３桁なので３bitです。

Ⅱ：いつ使うか、何が嬉しいのか

bit全探索は、探索するものの母数が少ないときに使えます。先ほどの例でいえば、「７枚のカードの中から～」などです。大体２０枚より大きくなると計算量が大きくなってしまうので向いていません。例えば１００枚のカードの中から総和を列挙するとなるとめちゃくちゃ時間がかかります。

全探索の嬉しいところは、選ぶ枚数が決まっていない問題に非常に便利なところです。普通の全探索では選ぶ枚数を１枚などに固定した場合の列挙は得意ですが、今回のように「好きな枚数のカードを選ぶ」場合は向いていません。

Ⅲ：bit全探索のしくみ

カードを配列で表します。

int a[3] = {1,2,3};

それぞれのbit列について、１となっているときに数字を変数numに足しましょう。
＜bit = 二進数で011の時＞

int num = a[0]+a[1]; // カード1とカード2を足す。
printf("%d",num); //3

大まかな流れは以上です。

Ⅳ：コード

実行結果

number:0
number:1
number:2
number:3
number:3
number:4
number:5
number:6

①(1<<n)

これは「二進数である１を左にn桁移動しろ」という文章です。
(1<<3)であれば、「2進数である１を左に３桁移動しろ」という文章です。

ちなみに(1<<3)は１０進数で表すと８です。３桁のbit列を考えたいときは（３枚のカードの中から考えたい場合は）２の３乗である８未満までの数字を考えましょう。実際、
０：000
１：001
２：010
３：011
４：100
５：101
６：110
７：111

０から８未満の数字で全てのbit列を列挙できます。

②(bit & (1<<i))

i = 0～2までfor文で回しているので、1を一度も左に移動しないとき、１回移動するとき、２回移動するときを考えます。変数bitにはbit列が入っています。

&はビット演算子と呼ばれる演算子の一つで、＆を挟む両端のビット列が両方とも１の時にtrue、つまりif文内の命令を実行します。変数bitのビット列を一桁ずつ調べ、１である桁があった場合は、対応する配列aの要素を変数numに足します。

bitが５となっている場合は以下のようにしてnumが求まります。

これをbit が０から７まで行うと、考えられるカードの和を列挙できます。

Ⅴ：練習問題

1,2,3,5,8,9,12が書かれた7枚のカードがあります。これから好きな枚数のカードを取り出した時、和が偶数かつ選んだ枚数が奇数になるものは何通りあるか答えよ。

解答
↓
↓
↓
いくつか別解があるかもしれませんが、bit全探索で解くことができます。

#include<stdio.h>
#define N 7
int main(void)
{
	int a[N] = { 1,2,3,5,8,9,12 };
	int bit, i;
	int sum = 0, count = 0 , num;

	for (bit = 0; bit < (1 << 7); bit++) {
		num = 0;
		count = 0;
		for (i = 0; i < 7; i++) {
			if (bit & (1 << i)) {
				num += a[i];
				count++;
			}
		}
		if (num % 2 == 0 && count%2==1) {
			sum++;
		}
	}

	printf("ans:%d", sum);
	return 0;

結果

ans:32

以下の問題はAtCoderにあったbit全探索の問題です。

最後に

コード文を一行ずつ読んでみて、分からない部分を一つずつ潰しましょう。

bit全探索は名前は難しそうですが要はただの全探索です。苦手意識を持たずに、頑張りましょう。