![[C#] bit全探索の使い方と実装、例題を解く](https://webbibouroku.com/wp-content/uploads/eye_atcoder.png)
bit全探索の使い方まとめ
C# で bit全探索 を実装する方法をまとめます。ちょうど前回の ABC でこれを使う問題に出くわしたので復習もかねてまとめます。
bit全探索を使う場面
上記のような問題がbit全探索を使える問題です。
ON/OFF, YES/NO, 1/0 のようにbool値で状態を表せるものの組み合わせを全列挙する場合に使います。ただし、多くの場合bit全探索でなくとも、深さ優先探索(DFS)で解くことができます。
例えば人が3人いて、みな「正直者」と「不親切な人」のいずれかだとします。このとき「正直者」と「不親切な人」の組み合わせを考えると、正直者=1, 不親切な人=0 としたときに
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1この8パターンが全てです。各人が「正直者」と「不親切な人」の2パターンなので 2^3=8 パターンとなります。N人いるときの組み合わせは 2^N 通りとなります。
bit列を使って状態を表現する
上の例で出した3人のパターンをよく見ると2進数の連番になっていることがわかります。
0: 000 不親切 不親切 不親切
1: 001 不親切 不親切 正直
2: 010 不親切 正直 不親切
3: 011 不親切 正直 正直
4: 100 正直 不親切 不親切
5: 101 正直 不親切 正直
6: 110 正直 正直 不親切
7: 111 正直 正直 正直つまり0以上2^N未満の整数がそれぞれ異なるパターンを表現しているということです。k桁目のbitが 1 であれば「true(正直者)」、0 であれば「false(不親切な人)」を表しています。
bit演算でk桁目のbitを取り出す
勝手がわかればあとはk桁目のbitを取り出す方法を考えます。使うのは bitシフト と AND演算 です。
bitシフト
たいていのプログラミング言語にはシフト演算しが用意されており、C#ももちろんシフト演算子(>>, <<)があります。シフトには右にシフトする演算子と左にシフトする演算子がありますが、今回使用するのは右にシフトする演算子(>>)のみです。
例えば整数値5を右に2ビットシフトするには次のようにします。
// 5: 101 -> 001
5 >> 2 ビット列の右2列分を破棄し、上位桁を右にシフトしています。左端の方の桁には0が埋められると覚えておけばとりあえずはOKです。
こうすることで2桁目のbitが右端0桁目まで降りてきたことがわかります。
後はこの右端のbitが 0 なのか 1 なのかを判定します。
AND演算
bit列の AND演算 は各bitごとにAND演算を行います。2数の各bitを突き合わせ、ともに1のときにその桁を1とします。
例えば x & 1 は変数xの最下位bitが0の場合0、1の場合1を返します。右端以外の桁は1とAND演算を行っているためすべて0になります。
つまり10進数5を2進数で表した時の、2桁目の値は次のようにして求められます。
(5 >> 2) & 1演算子の優先度の関係で括弧は必須です。
右にK回シフトして1でAND
Xを右にK回シフトして1でAND演算 することでxの右からk桁目の値(1/0)を取得できます。
これで各bitの値を取得できるようになったので、bit全探索を使って探索を行えるようになりました。
bit全探索の例
// 3桁のbit列で全探索を行う
for (int x = 0; x < Math.Pow(2, 3); x++)
{
var array = new bool[3];
// 右からk桁目を取り出す
for (int k = 0; k < 3; k++)
{
var y = (x >> k) & 1;
array[2 - k] = y==1;
}
}こんな感じで8パターンの状態を探索できます。
例題をとく
C – HonestOrUnkind2
var data = new Tuple<int, int>[N][];
// 入力は省略 ..
var ans = 0;
// bit全探索でN人の状態を探索する
for (int i = 0; i < Math.Pow(2, N); i++)
{
// N人の状態をbool[]にする
var katei = new bool[N];
for (int j = 0; j < N; j++)
{
var x = (i >> j) & 1;
if (x == 1) katei[j] = true;
}
// この状態での判定
var ok = true;
for (int j = 0; j < N; j++)
{
if (katei[j])
{
for (int k = 0; k < data[j].Length; k++)
{
var x = data[j][k].Item1;
var y = data[j][k].Item2 == 1;
if (katei[x] != y) ok = false;
}
}
}
if (ok)
{
ans = Math.Max(ans, katei.Count(f => f));
}
}bit全探索についての例なので入力は省いています。あと、判定前にわかりやすく bool[] に置き換えてますが、別にしなくてもいいです。
C – Switches
var ans = 0;
// bit全探索
for (int i = 0; i < Math.Pow(2, N); i++)
{
var light = new bool[N];
for (int j = 0; j < N; j++)
{
light[j] = ((i >> j) & 1) == 1;
}
// 判定
var ok = true;
for (int j = 0; j < M; j++)
{
var count = 0;
for (int k = 0; k < S[j].Length; k++)
{
if (light[S[j][k]]) count++;
}
count %= 2;
if (P[j] != count % 2) ok = false;
}
if (ok) ans++;
}bit全探索は競技プログラミングだと問題文がややこしくなる印象なので、慣れが必要かなと思います。
実務だと enum + ビット演算でやるのも選択肢の1つです。
以上。
