bit全探索について

前回の終わりに、今回は自作した対戦ゲームについて書くと書いたのですが、予定を変えて忘れないうちにメモをしておきます。
今回はAtCoderについての記事です。

前回の参加記事はこれです。
これから地道に勉強していくので、温かく見守っていただけたら嬉しいです。
developer-bpeldi2oerkd8.hatenablog.com

bit全探索とは

部分集合の全列挙や、2種類の選択のすべての組み合わせを調べる方法のこと。

とにかく2択の選択をn回繰り返すときに使います。

全部で2^n通りあるので、計算が間に合う場合にのみ使います。（間に合わない場合はbitDPなどを使うらしい）

2択はそれを選択するか選択しないかというシチュエーションでよく出てきます。（有名なものだと、数字の間に+を入れるか入れないかなど）

どのように解くのか(Javaの場合)

次のように書く。注意しないといけないのは、JavaではC++と違って、フラグが立っているかの判定を下のようにしないとエラーが出ること(よくネットで見るC++だと、if(i & (1 << j))となっているがこれではエラーが出る)

for(int i=0; i<(1 << N); i++) {
	for(int j=0; j<N; j++) {
                //フラグが立っているか
		if((1 & (i >> j)) == 1) {
			//ここに処理を書く(あるなしでいうとある場合)
		}else {
			//ここに処理を書く(あるなしでいうとない場合)
		}
	}
}

なぜこれで解けるのか

先ほど書いたように、2択をn回行うので全部で2^n通りになる。
このすべてについて2進数で表現すると、すべての場合を全列挙できる。

例えば、1~3の数字の集合の部分集合は、各数字を選択する・選択しないの2択で考えると、2^3=8通りになる。
そこで0~7の数字を2進数で表現すると下のようになる。一番最初の行は各列がどの数字に対応するかを表している。（1のとき集合に入れる）

3 2 1
0 0 0 -> {}
0 0 1 -> {1}
0 1 0 -> {2}
0 1 1 -> {1,2}
1 0 0 -> {3}
1 0 1 -> {1,3}
1 1 0 -> {2,3}
1 1 1 -> {1,2,3}

このようにすべての部分集合を全列挙できている。
誰が考えたのか知らないが、頭良すぎです。

次回こそは、対戦ゲームの説明ができるかなと思います。
（このままだと、Atcoderだけのブログになってしまうので）