競技プログラミング講習/bit全探索

概要

今回は、bit全探索について解説します。
bit全探索は、ABCのC問題あたりでよく出題されています。bit全探索と同等のことはDFSでもできます。しかし、bit全探索の方が実装が軽く、実行速度もやや早いです。使えるようにしておきましょう。

重要語

bit全探索

2進数とビット演算を用いてある集合の部分集合を全探索できる

必要語

今回の必要語はありません。

bit全探索

2進数を用いてある集合の部分集合を全て列挙していくことができます。例えば、{0, 1, 2}の部分集合は、 {0, 2}や{1}や{}（空集合）などです。

部分集合の表現

まず、N個の整数A0, A1, ... An-1からいくつかを選ぶということを考えてみましょう。 それぞれの整数Aiに対して選ぶ/選ばないという選択をすることになりますから、選び方は全部で2N通りです。 n=3の時に考えてみると、 {}, {A0}, {A1}, {A0, A1}, {A2}, {A0, A2}, {A1, A2}, {A0, A1, A2} の8（=23）通りあります。 ここで、Aiを選ぶことを1、選ばないことを0として2進数のiビット目（右から0,1,2...と数えることにします）と対応させてみましょう。 そうすると、各集合を2進数で表すことができます。例えば、{A0, A1}は011、 {A2}は100、{}は000のようになります。 このようにすると、各集合は000, 001, 010, 011, ... 111となり、10進数にすると0, 1, 2, 3, ... 7となります。

部分集合の列挙

このように2進数によって部分集合を表現すれば、これらは10進数で0, 1, 2, 3, ... 2N-1となるため、 通常のforループで列挙することができます。2N-1まで回すため、継続条件式を b < pow(2, n); とpow関数を使って書きたくなりますが、この書き方はあまりよくありません。2Nは整数ですが、 pow関数は小数で計算するため、誤差が出る可能性があるためです。また、仮に偶然うまく判定されたとしても、実行速度が遅いです。 ではどうすればいいかと言うと、 b < 1 << n です。<（左不等号）と<<（左シフト） では<<のほうが優先順位が高いので、 b < (1 << n) と解釈されます。2Nと1 << n の値は等しいですから、2N-1まで回すことができます。 2をN回かけて計算してもいいですが、こちらのほうが簡潔で実行速度は断然速いです。 
for (int b = 0; b < 1 << n; b++) {
    // bが部分集合を表す
}

部分集合の探索

部分集合が列挙できたところで、どの要素を取るのかを復元してみましょう。 bのiビット目がAiに対応していますから、この判定は以下のようになります。 例えば、0b10110101（=b）から4（=i）ビット目を得たいとします。まず、bをiビット右にシフトすると0b10110となり、 得たいビットが0ビット目に来ました。この0ビット目以外の情報は必要ないため、 & 1をしてマスクをかけます。 そうすると、この値が1のときはbの要素としてにAiは含まれますが、0のとき含まれませんから、この式をそのまま ifに入れてやればよいです。 
if ((b >> i) & 1) {
    // もし部分集合bにa[i]が含まれるなら
}

実装例

以上のことをまとめて実装すると、以下のようになります。 N個の整数A0, A1, ... An-1からいくつかを選んで和をKにできるかどうか判定します。 計算量はO(2N)のため、1≤N≤20ほどが現実的です。なお、この問題設定では、DPという手法を用いることで、O(NK)で判定できます。
bit全探索 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    bool ok = false;
    for (int b = 0; b < 1 << n; b++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if ((b >> i) & 1) {
                sum += a[i];
            }
        }
        if (sum == k) ok = true;
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

ビット演算(おまけ)

AND、OR、XOR、NOT、左シフト、右シフトを紹介します。ビット単位の演算を行います。

AND

特定のビット以外を0にしたいときに使用します。AND演算の特性上、 a & bの結果は、bが1である部分はそのまま残り、0である部分は0になります。
AND 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 0b10010101, b = 0b00111100;
    int c = a & b;
    /*
    a | 0b10010101
    b | 0b00111100
    --------------
    c | 0b00010100 = 0x14
    */
    printf("%02X", c);
    return 0;
}

OR

特定のビットを1にしたいときに使用します。OR演算の特性上、 a | bの結果は、bが1である部分は1になり、0である部分はそのまま残ります。
OR 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 0b10010101, b = 0b00111100;
    int c = a | b;
    /*
    a | 0b10010101
    b | 0b00111100
    --------------
    c | 0b10111101 = 0xBD
    */
    printf("%02X", c);
    return 0;
}

XOR

特定のビットを反転したいときに使用します。XOR演算の特性上、 a ^ bの結果は、bが1である部分は反転し、0である部分はそのまま残ります。
XOR 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 0b10010101, b = 0b00111100;
    int c = a ^ b;
    /*
    a | 0b10010101
    b | 0b00111100
    --------------
    c | 0b10101001 = 0xA9
    */
    printf("%02X", c);
    return 0;
}

NOT

全てのビットを反転したいときに使用します。NOT演算は全て反転してしまうため、 0xFが前に余計につくことが多いです（もちろんそれが必要ならいいですが）。 XOR演算のほうが特定のビットを反転できるため、NOT演算は使うことはあまりありません。
NOT 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 0b10010101;
    int b = ~a;
    /*
    a | 0b00...010010101
    -------------------
    b | 0b11...101101010 = 0xFFFFFF6A
    */
    printf("%08X", b);
    return 0;
}

左シフト

全てのビットを左にシフトしたいときに使用します。空いたビットは0で埋められ、はみ出たビットは無視されます。 左シフト演算の特性上、nビット左にシフトすると、値は2n倍になります（オーバーフローしなければ）。
左シフト 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 0b10010101;
    int b = a << 3;
    /*
    a | 0b000010010101 = 0x095 =  149
    ------------------
    b | 0b010010101000 = 0x4A8 = 1192
    */
    printf("%03X", b);
    return 0;
}

右シフト

全てのビットを右にシフトしたいときに使用します。空いたビットは0で埋められ、はみ出たビットは無視されます。 右シフト演算の特性上、nビット右にシフトすると、値は2n分の1になります（小数部は捨てられる）。
右シフト 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a = 0b10010101;
    int b = a >> 3;
    /*
    a | 0b10010101 = 0x95 = 149
    --------------
    b | 0b00010010 = 0x12 =  18
    */
    printf("%02X", b);
    return 0;
}

注意点

ビット演算で最も注意するべき点は優先順位です。特に、& | ^より ==（等価）や<（左不等号） といった比較演算子の方が優先順位は高いことに注意してください。例えば以下のプログラムは、xが偶数かどうかを判定することを意図したものですが、 x & 1 == 0 の部分は、(x & 1) == 0 ではなくx & (1 == 0) と解釈されてしまい、正しい結果を得られません。ビット演算をしていてどっちの方が優先順位が高いのかがわからなくなったら、調べてみるのも大切ですが、()でくくってあげると確実です。 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int x;
    cin >> x;
    if (x & 1 == 0) { // 間違い
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}