典型的アルゴリズムについて(２)

前置き

プロコンの典型アルゴリズムに関する記事（第２回）を書く。

取り上げるもの

変数 $x_{i} \in \{0,1\}, i = 0..n$ について全探索をすること。(bit全探索とかいうのでしょうか？）計算量は当然変数の数に対して指数オーダなので、大規模な問には使えない。

例えば下記が例題となる。
No.43 野球の試合 - yukicoder
総当たりリーグ戦が途中まで終わっている状況で、残りの試合が終わったとき、指定のチームが最高何位になれるかを求める。これはまだ試合していない所について、勝敗の組み合わせを全通り試せばOK。

サンプル

for (int i = 0;i < (1 << M);i++){
	for (int j = M-1; j>=0 ;j--){
		if(i >> j & 1){
		}
	}
}

M個の変数についてこれで探索できる。初めてみた時はちょっと面食らった。
$i$ は、長さ $M$ のbit列に対応する。例えば $M = 2$ としたとき、 $i$ は0から3となり、bit表記するとそれぞれ $\{00,01,10,11\}$ となる。これはすなわち2変数のとりうる組み合わせを列挙している。
$j$ は、左から順にbitが1であるかを判断している。