0. はじめに

ビット演算については、以下の記事で特集しました。

qiita.com

しかし、この中で、bit 全探索に関する説明がだいぶ簡潔すぎたので、ちゃんと書きたいなと思って、この記事書きます！！！ただし、ビット演算に関する知識は前提としているので、そこに不安のある方は上の記事を読んでもらえたらと思います。

具体的には、以下の表を見てピンとこなかった場合には、先に上記の記事を読んでもらえたらと思います。

f:id:drken1215:20200304160727p:plain

なお、この記事は、

Competitive Programming (1) Advent Calendar 2019

の 6 日目の記事として書きました。

1. bit 全探索で何ができるか

bit 全探索とは、

$N$ 個のものから、いくつか選ぶ方法を全列挙して調べ上げる手法

です！！！ $N$ 個のものからいくつか選ぶ方法は、 $2^{N}$ 通りの選択肢があります。たとえば $N = 3$ のとき、3 個のアイテム {2, 1, 0} からいくつか選ぶ方法は下図のように $2^{3} = 8$ 通りあります！！！

ここで、「まったく選ばない」という方法も含めていることに注意しましょう

f:id:drken1215:20191214160849p:plain

bit 全探索が使いこなせると、たとえばこんな問題が解けるようになります！！！

$N$ 個の正の整数 $a_{0}, a_{1}, \dots, a_{N-1}$ と、正の整数 $W$ とが与えられます。
$a_{0}, a_{1}, \dots, a_{N-1}$ の中から何個か選んで総和を $W$ とすることができるかどうかを判定してください。

$1 \le N \le 20$

この問題はまさに「 $N$ 個の品物から何個か選ぶ」という方法をすべて調べつくすことで解くことができます。

2. bit 全探索の考え方

突然ですが、上図の $2^{3} = 8$ 個の選択肢は、それぞれ下図のように「1 つの数値」で表すことができます！！！！！

f:id:drken1215:20191220124759p:plain

このように、bit 全探索は、

$N$ 個のアイテムからいくつか選ぶ方法 ( {2, 1} とか )
整数値 ( 6 とか )

とを一対一に対応付ける手法です。具体的な対応方法を考えます。たとえば $N = 3$ 個のアイテム {2, 1, 0} に対して、 {2, 1} を選ぶ方法について考えてみると、

二進法表記で $N$ 桁のビット列を考えて、1 桁目と 2 桁目に 1 が立っているものを考えます： 110　(0 桁目が一番右で、2 桁目が一番左です)
これを十進法に直します：6

たったこれだけです！！！

$N$ 個のアイテムからいくつか選ぶ方法は $2^{N}$ 通りありますが、それらに対して $0, 1, 2, \dots, 2^{N}-1$ という整数値に対応付けることができます。bit 全探索で

for (int bit = 0; bit < (1<<N); ++bit) {

}

というコードを書くのは、まさにそのことを表しています。「いくつか選ぶ方法」を bit という整数に対応付けているのです。

次に、逆のことを考えてみましょう。つまり、

bit という整数値が
どういう「選び方」を表しているのか

を解釈し直す必要があります。せっかく「いくつか選ぶ方法」を 1 つの整数値で巧みに表すことができても、その整数が「どう選ぶことを意味しているのか」がわからないと、何もできません...

3. 整数値から、「いくつか選ぶ方法」への復元

おそらくこの部分が、bit 全探索において、多くの方が「これなにやってるの！？」となる部分かもしれません。下のようなコードをよく見ると思います。これは、実は、まさに復元処理をやっているのです。

if (bit & (1 << i)) {

}

整数値 bit から、「いくつか選ぶ方法」を復元する方針は、実はとても単純明快です。　

【方針】

$i = 0, 1, \dots, N-1$ のそれぞれについて、整数値 bit で表される「選び方」において、「 $i$ を選ぶかどうか」を判定する。

これさえできれば、整数値 bit から、「いくつか選ぶ方法」を復元することができます。ここで具体例として、 $N = 5$ 、 ${\rm bit} = 13$ を考えてみます。 $i = 0, 1, \dots, N-1$ に対して、「bit & (1 << i)」の値がどうなるかを見てみましょう。なお、bit = 13 はビット列で表すと

bit = 01101

であることに注意します。

i	1 << i	bit & (1 << i)
0	00001	01101 & 00001 = 00001 (True)
1	00010	01101 & 00010 = 00000 (False)
2	00100	01101 & 00100 = 00100 (True)
3	01000	01101 & 01000 = 01000 (True)
4	10000	01101 & 10000 = 00000 (False)

なんと見事に、

$i$ が ${\rm bit}$ に含まれているとき、bit & (1 << i) は True
$i$ が ${\rm bit}$ に含まれていないとき、bit & (1 << i) は False

となっています！！！1 個 1 個紐解くと、以下のような感じです。

(1 << i) とは、i 桁目のみが 1 で他は 0 であるようなビット列である
bit & (1 << i) というのは、i 桁目のみを残して他の桁はすべてふるい落として 0 にしてしまう処理である
よって
- bit の i 桁目が 1 であれば、bit & (1 << i) の i 桁目が 1 で残ります (他の桁はすべて 0)
- bit の i 桁目が 0 であれば、bit & (1 << i) の i 桁目が 0 になります (すべての桁が 0)

つまり (1 << i) というのは、i 桁目のみを残して他の桁を 0 にしてしまうフィルターの役割を果たします。

この考え方は、bit 全探索以外でも、複数本のフラグを管理する場面でしばしば用います。電子工作なんかをやってると、 $N$ 個の LED のうちのどれが光っているかをビット列 ${\rm bit}$ で管理します。そのときに $i$ 番目の LED が光っているかどうかを、まさに下のような書き方で調べたりします。

if (bit & (1 << i)) {

}

まとめると、int 型から「いくつか選ぶ方法」への変換は以下のようなコードでできます。これは、int 型変数 ${\rm bit}$ を引数として受け取って、それに対応する「どのアイテムを選ぶのか」を返す関数です。

// int 型を「どのアイテムを選ぶのか」を表す vector<int> 型に変換
// bit: 集合を表す整数
// N: 何個のものについて考えているか
vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

細かい注意点 1

実装上は、vector 型の集合 S を明示的に宣言することはあまり多くないです。実際は

各 i = 0, 1, ... に対して
i が bit で表される集合に含まれることがわかったら
それに応じた処理をその場で行ってしまう

という実装をすることが多いように思います。

細かい注意点 2

if (bit & (1 << i))

という書き方には、もう一つの書き方もあります。

if ((bit >> i) & 1)

4. bit 全探索の例

それでは具体的な問題を解いていきましょう！！！

例題 1：部分和問題

まずは、bit 全探索の基本問題・部分和問題から行きます。

問題概要

$N$ 個の正の整数 $a_{0}, a_{1}, \dots, a_{N-1}$ と、正の整数 $W$ とが与えられます。

$a_{0}, a_{1}, \dots, a_{N-1}$ の中から何個か選んで総和を $W$ とすることができるかどうかを判定してください。

制約

$1 \le N \le 20$

解法

この問題は、

$N$ 個のものからいくつか選ぶ $2^{N}$ 通りの方法を全探索して
選んだ総和が $W$ に一致するものがあるかどうかを判定する

という bit 全探索法のためにあるような問題ですね！まずは、簡潔なコーディングを意識せずに、愚直に「int 型を vector 型に変換する」という方針で解いてみましょう。

計算量は、 $2^{N}$ 通りそれぞれについて、調べるのに $O(N)$ だけかかるので、 $O(N2^{N})$ となります。

#include <iostream>
#include <vector>
using namespace std;

// int 型を vector 型に変換
// bit: 集合を表す整数
// N: 何個のものについて考えているか
vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

int main() {
    // 入力
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // bit 全探索
    bool exist = false;
    for (int bit = 0; bit < (1 << N); ++bit) {
        // どれを選ぶか
        vector<int> S = IntegerToVector(bit, N);

        // 部分集合に対応する総和
        int sum = 0;
        for (int i : S) sum += a[i];

        // 判定
        if (sum == W) exist = true;
    }

    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
}

実装を柔軟に簡潔に

慣れてきたら、もう少し簡略化して、

整数値 bit で表される「選び方」において、アイテム $i$ を選ぶのかどうかを判定する
含まれるならそれに応じた処理

をまとめてやってしまいましょう。以下のように書けます。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // bit 全探索
    bool exist = false;
    for (int bit = 0; bit < (1 << N); ++bit) {
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            if (bit & (1 << i)) sum += a[i];
        }

        // 判定
        if (sum == W) exist = true;
    }

    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
}

例題 2： AtCoder ABC 147 C - HonestOrUnkind2

ついこないだの ABC で出題されて、「令和 ABC の C 問題で最も難しい問題」として話題になった問題ですね！！

$N$ 人のうち、「誰が正直者なのか」を選ぶ方法は $2^{N}$ 通りあります。それを全部調べ上げます！！！

問題概要

$N$ 人がいて、それぞれ「正直者」であるか、「不親切な人」であるかのいずれかです。

「正直者」は、必ず、正しいことを語る
「不親切な人」は、真偽不明のことを語る (正しいかや誤りかはわからない)

今、 $N$ 人がそれぞれ次のように語りました。

人目は、個の証言を語った
- 人目による個目の証言は以下のいずれかである
  - $x_{i, j}$ さんは「正直者」です ( $y_{i, j} = 1$ )
  - $x_{i, j}$ さんは「不親切な人」です ( $y_{i, j} = 0$ )

$N$ 人それぞれの「正直者」であるか「不親切な人」であるかのパターンのうち、以上の証言に矛盾しないものはいくつか考えられます (0 通りもありえます)。そのうち、正直者が最も多いパターンでは、正直者は何人でしょうか？

制約

$1 \le N \le 15$

解法

この問題は、とにかく方針決めが大切です。以下のような思考に走ってしまうと、迷走します...

とりあえず、誰かを正直者に決めてみよう...
人 A を正直者と仮定すると、その人の証言から、B さんと C さんは正直者で、D さんは不親切ということになって...
そうすると、また B さんが正直者ということから、B さんの証言から...

人間がこの種のパズルを解くとき、こういう風に解くと思いますが、この方針でやると辛いです。

そこで、次のように考えてみましょう

誰が正直者で、誰が不親切なのか、完全に決め打ちしてしまう。そのパターンは $2^{N}$ 通りある
その決め打ちが整合しているのかどうかを check する。つまり、証言と矛盾しないかどうかを check する
check が通ったものについて、正直者の人数を数える。その最大値を出力する。

ポイントは、「誰が正直者で誰が不親切なのかを完全に決め打ちすると、全員の証言が整合しているかどうかを簡単に確認できる」という点です。実装してみましょう。

#include <iostream>
#include <vector>
using namespace std;

// 1 つの証言を表す構造体
using pint = pair<int,int>; // 「人」と「0 or 1」

// 入力
int N;
vector<vector<pint>> v;

// 整数 bit に対応する「決め打ち」が整合しているかを判定
bool judge(int bit) {
    
    // i 人目の証言を検証する
    for (int i = 0; i < N; ++i) {
        
        // i 人目が「不親切」だったら、証言はすべて無意味
        if ( !(bit & (1 << i)) ) continue;

        // それぞれ確認
        for (pint xy : v[i]) {
            int x = xy.first; // x が
            int y = xy.second; // y = 1: 正直、y = 0: 不親切

            // y = 1 なのに「不親切」だったらダメ
            if (y == 1 && !(bit & (1 << x))) return false;

            // y = 0 なのに「正直者」だったらダメ
            if (y == 0 && (bit & (1 << x))) return false;
        }
    }
    return true;
}


int main() {
    cin >> N;
    v.resize(N);
    for (int i = 0; i < N; ++i) {
        int A; cin >> A;
        v[i].resize(A);
        for (int j = 0; j < A; ++j) {
            cin >> v[i][j].first >> v[i][j].second;
            --v[i][j].first; // 0-indexed に
        }
    }

    int res = 0;
    for (int bit = 0; bit < (1 << N); ++bit) {
        
        // 矛盾 check
        if (judge(bit)) {
            
            // bit に含まれる人数を数える
            int count = 0;
            for (int i = 0; i < N; ++i) {
                if (bit & (1 << i)) ++count;
            }
            res = max(res, count);
        }
    }

    cout << res << endl;
}

発展技 1：証言 check

上のコードの

// y = 1 なのに「不親切」だったらダメ
if (y == 1 && !(bit & (1 << x))) return false;

// y = 0 なのに「正直者」だったらダメ
if (y == 0 && (bit & (1 << x))) return false;

の部分は、まとめて次のように書けます

if ( ((bit >> x) & 1) ^ y ) return false;

5. 最後に

bit 全探索の問題はとかく「制約が小さいから bit 全探索が想定なのは明らか」と言われがちです。しかし、この視点は重要なことを見落としてしまいそうな危惧があります。それは

「どこを決めれば全体が決まるか」という視点を忘れずに考察することは、制約が大きくても重要

だと思うからです。そして、特に「正直者と嘘つきの問題」には、以下の重要な教訓が含まれていると思います。

問題に対して初めから数学的考察ばかりに走ってしまうのは危険で、数学じゃなくて探索でできるなら探索すべきである
数学的考察は、探索範囲を絞るために使う (そのパターンは本当に無数にある)

本当の高難易度問題になると、この通りに行くかはわからないのですが、700 点問題までであれば、上記の心構えで解けるように思います。過度に数学的考察に走るのではなく、探索すべきところはしっかり探索できるようにすることが大事かなと...自戒も込めて。

それでは、すてきな bit 全探索ライフを！！！
bit 全探索の次は、bit DP も！！！

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

bit 全探索

0. はじめに

1. bit 全探索で何ができるか

2. bit 全探索の考え方

3. 整数値から、「いくつか選ぶ方法」への復元

細かい注意点 1

細かい注意点 2

4. bit 全探索の例

例題 1：部分和問題

問題概要

制約

解法

実装を柔軟に簡潔に

例題 2： AtCoder ABC 147 C - HonestOrUnkind2

問題概要

制約

解法

発展技 1：証言 check

5. 最後に

0. はじめに

1. bit 全探索で何ができるか

2. bit 全探索の考え方

3. 整数値から、「いくつか選ぶ方法」への復元

細かい注意点 1

細かい注意点 2

4. bit 全探索の例

例題 1： 部分和問題

問題概要

制約

解法

実装を柔軟に簡潔に

例題 2： AtCoder ABC 147 C - HonestOrUnkind2

問題概要

制約

解法

発展技 1： 証言 check

5. 最後に

例題 1：部分和問題

発展技 1：証言 check