bit全探索をココロから理解する

投稿日: 2023-01-09 更新日: 2026-03-20

目次
はじめに
bit 全探索とは
まずは例から
bit 全探索の実装
いくつか選ぶ方法を 2 進数で表す
2 進数 →10 進数に変換する
bit 全探索するための for 文
10 進数 →2 進数に変換し、選ぶ方法を復元する
実践問題
部分和問題
ABC289 C - Coverage
ABC264 C - Matrix Reducing
さいごに
練習問題
参考文献

はじめに

bit 全探索は競プロで全探索アルゴリズムを初めて学ぶ人にとって最初の壁となると思います。僕自身も初めて学んだのが bit 全探索であり、学ぶ際に色々苦労しました。

この記事では、その bit 全探索について初めて学ぶ方でも分かりやすく説明したいと思います。なお、前提知識として2 進数・10 進数の基本知識、ビット演算(シフト演算、AND 演算) が分かると、より理解が深まると思います。

bit 全探索とは

まず、bit 全探索について一言で説明すると

$2^N$ 通りある $N$ 個のものから、いくつか選んだ組合せを全探索するアルゴリズム

となります。これだけ言われてもよくわからないと思うので、例を通して説明していきます。

まずは例から

$N$ 個のものから、いくつか選んだ組合せをいきなり考えるのは難しいので、より簡単な例題 1 を考えます。

例題 1

【問題】
$3$ 個の整数 $0,1,2$ が与えられたとき、その中からいくつか選ぶ方法を列挙せよ。

表に書き出すと $8$ 通りあることが分かります。

なぜ $8$ 通りなのかを知るために整数がどのように選ばれているのかを考えます。
3 個の整数 $0,1,2$ は

$0$ を選ぶ or $0$ を選ばない
$1$ を選ぶ or $1$ を選ばない
$2$ を選ぶ or $2$ を選ばない

の選択肢が存在します。つまり、1 つの整数ごとに選択肢が 2 通り存在します。
よって、表に書いた通り 3 個の整数の中からいくつか選ぶ方法は $2\times2\times2 = 2^3$ つまり $8$ 通り存在します。一般に $N$ 個のものからいくつか選ぶ方法は $2^N$ 通り存在することが知られています。

すなわち、以下のような問題

$N$ 個あるものから、それぞれ「選ぶ」「選ばない」などの1 個のものにつき 2 通りある選択肢がある場合、 $2^N$ 通りの組合せを全探索する¹

を bit 全探索を使うことでとても簡潔に実装することができるようになります。

続いて、こちらの例題 2 を考えていきます。

例題 2

【問題】
$N$ 個の整数 $0, 1, \dots, N - 1$ が与えられたとき、その中からいくつか選ぶ方法を列挙せよ。
【制約】
$N \leq 20$

例題 2 は例題 1 よりも $N$ の制約が緩くなりました。(例題 1 は $N=3$ の場合です)
この問題を愚直に for ループで解こうとすると、$N$ 重の for 文が必要になります。また、 $N$ の値は変わるので for 文の数を固定して書くことができず、実装がとんでもないことになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
            for (int l = 0; l < 2; l++) {
                for (int m = 0; m < 2; m++) {
                    // ... 何重のfor文か分からない
                }
            }
        }
    }
}

ここで、bit 全探索を使うと $N$ 重の for 文を書くことなく、簡単に実装できるようになります！早速、例題 2 を解く bit 全探索を実装していきましょう。

bit 全探索の実装

bit 全探索の基本的な実装方針を記します。
なお、以下から 「 $2^N$ 通りある $N$ 個のものから、いくつか選んだ組合せ」 のことをわかりやすく簡略化して 「いくつか選ぶ方法」 と表記します。

💡 方針
手順 1: 「いくつか選ぶ方法」を 2 進数で表し、全探索しやすいように 2 進数 →10 進数に変換にする
手順 2: 「いくつか選ぶ方法」を復元するため、10 進数 →2 進数に再び変換する
手順 3: 復元した「いくつか選ぶ方法」について処理を行う
手順 4: 手順 1-3 を $2^N$ 通り全てに行う

いくつか選ぶ方法を 2 進数で表す

いきなり結論ですが、「いくつか選ぶ方法」を 2 進数でこのように表すことにします。

$i$ 番目のものを選ぶなら、2 進数の右から $i$ 桁目を「1」にする
$i$ 番目のものを選ばないなら、2 進数の右から $i$ 桁目を「0」にする

言うなれば、選ぶなら「0」、選ばないなら「1」と 2 進数で表現するということなのですが、これを例題 1 の $8$ 通りの選び方について、具体的に図で表すとこのようになります。

例えば、3 個の整数 $0,1,2$ に対して $1,2$ を選ぶ方法 $\{1,2\}$ は

1 番目の $0$ : 選ばない
2 番目の $1$ : 選ぶ
3 番目の $2$ : 選ぶ

となっています。これを 2 進数で復元する際、 選ぶときを「1」、選ばないときを「0」 としたとき、2 進数では $110_{(2)}$ と表すことができます。このように、選んだものに対応して 2 進数の桁が 1 になっています。

2 進数 →10 進数に変換する

次に、選ぶ方法を表した 2 進数を 10 進数へと変換します。
例題 1 の $8$ 通りの選び方について、2 進数と 10 進数ではこのように表すことができます。

bit 全探索するための for 文

$2^N$ 通りある組合せの方法 1 つ 1 つを 10 進数の $0,1,2,…,2^N-1$ に対応したことで for ループを用いて簡単に全探索することができます。以下のコードは変数bitを $0\sim 2^N-1$ の範囲で for ループを回しています。これは「いくつか選ぶ方法」を 10 進数に対応付けて全探索を行っていることを表しています。

1
2
3
for (int bit = 0; bit < (1 << N); bit++) {
    /* 「いくつか選ぶ方法」を10進数で表したものに対して処理 */
}

コード内の 1 << N は 1 を N 桁左ビットシフトした値 = $2^N$ のことです。(ビットシフトの詳細はアルゴ式のこのページを見てください。)

10 進数 →2 進数に変換し、選ぶ方法を復元する

「いくつか選ぶ方法」を 10 進数に対応させましたが、このままだと10 進数の値が表している「いくつか選ぶ方法」がなにを選んだのかが分からないので、先程と逆のことを行い復元します。つまり、

10 進数 $0,1,2,…,2^N-1$ を再び 2 進数で表す
$1 \leq i \leq N$ を満たす $i$ について、2 進数で表される「いくつか選ぶ方法」から「 $i$ 番目のものを選んだかどうか」を判定する

ことを行います。以下のコードはまさに 10 進数の値から「いくつか選ぶ方法」を復元しているのです。

1
2
3
4
// bitのi桁目(i番目のもの)は1(選んだ)かどうか
if ((bit >> i) & 1) {
    /* 選んだものに対して処理 */
}

このコードを詳しく見ていきます。この if 文は 10 進数の値 $0,1,2,…,2^N-1$ それぞれについて、

再び 2 進数で表したとき、 $i$ 桁目が 1 かどうか( $i$ 番目のものを選んだかどうか)

を判定しています。

例えば、$N=3,\text{bit} = 5$ のとき、if((bit >> i) & 1) はどのように判定を行うのか考えます。

$\text{bit}$ を 2 進数で表すと $101_{(2)}$ になるので $i = 0,1,2$ のときの判定は以下の通りです。

i	`(bit >> i)`	`((bit >> i) & 1)`	判定
0	101	101 & 001 = 001	True
1	010	010 & 001 = 000	False
2	001	001 & 001 = 001	True

(bit >> i)は 2 進数の $\text{bit}$ を $i$ 桁右シフトした値であり、これと $1$ を AND 演算で判定をすることで

$\text{bit}$ の $i$ 桁目の値が 1 のとき、True
$\text{bit}$ の $i$ 桁目の値が 0 のとき、False

となります。実際は $1$ と AND 演算することにより最下位 bit を残して全て 0 にできるので、

$\text{bit}$ の $i$ 桁右シフトした値の最下位 bit が 1 なら、True (最下位 bit 以外の全ての桁は 0)
$\text{bit}$ の $i$ 桁右シフトした値の最下位 bit が 0 なら、False (全ての桁は 0)

を判定していることになります。

よって、「いくつか選ぶ方法」を復元するためには、以下のように先程の判定を for ループで全てのものに対して行えば良いです。

1
2
3
4
5
for (int i = 0; i < N; i++) {
    if ((bit >> i) & 1) {
        /* 選んだものに対して処理 */
    }
}

以上のことを踏まえて例題 2 を bit 全探索で実装すると以下の通りになります！

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main() {
    // N: 何個のものについて考えているか
    // bit: 選び方の集合を表す10進数
    int N;
    cin >> N;

    // 2^N通りの選び方を 0,1,2,...,2^N-1 の10進数の値に対応させ、全探索
    for (int bit = 0; bit < (1 << N); bit++) {
        // 選んだものを管理する配列S
        vector<int> S;

        // 各iに対して
        for (int i = 0; i < N; i++) {
            // bitのi桁目は1(選んだ)かどうか
            if ((bit >> i) & 1) {
                S.push_back(i);  // 選んだならSに追加する
            }
        }

        // 配列Sの出力
        cout << bit << ": ";
        for (auto e : S) cout << e << " ";
        cout << endl;
    }
}

出力

if((bit >> i) & 1)はif(bit & (1 << i))と書くこともできますが、本質は同じです。

また、2 進数の bit に対して頻出な判定方法は以下の通りです。

判定	書き方
bit の $i$ 桁目が 1 か	`if((bit >> i) & 1)`
bit の $i$ 桁目が 1 でないか	`if(!((bit >> i) & 1))`
bit の 1 の個数	`__builtin_popcount(bit)`

計算量について

この先、アルゴリズムを学んでいく上で避けて通れないのは計算量の存在です。(計算量については APG4b のW - 2.06.計算量を見てください。)

「いくつか選ぶ方法」というのは $2^N$ 通りありますが、これは指数的に増加します。すなわち $N$ の値が大きくなると「いくつか選ぶ方法」の数は爆発的に増加します。競技プログラミングの実行制限時間は 2 秒前後であることが多いので、bit 全探索が想定解の場合の制約は $N \leq 20$ くらいの小さい値が限界です。 これ以上 $N$ の値が大きくなると、実行制限時間に間に合いません。bit 全探索を行う際は制約に注意しましょう。例題 2 を解いた実装は計算量だと $O(N 2^N)$ となります。

実践問題

それではここでいくつかの問題を bit 全探索で解いてみましょう。

部分和問題

https://algo-method.com/tasks/1083

【問題】
$N$ 個の整数 $A_0, A_1, \dots ,A_{N-1}$ と、整数 $V$ が与えられます。
これらの整数の中から、いくつかの整数を選んで総和をとります。総和を $V$ にすることが可能かどうかを判定してください。
【制約】
$1\leq N\leq 16$
$1\leq V\leq 10^8$
$1\leq A_i\leq V (0 \leq i\leq N-1)$

部分和問題という超ド定番の問題です。
bit 全探索の解説記事だから、bit 全探索で解くんだな～と分かってしまうのですが、一度 0 からこの問題の解法を考えましょう。

解法

まず初めに制約を確認しましょう。ここで分かる大事なことは

$N \leq 16$ と $N$ が非常に小さいこと
$A_i \leq 10^8$ と 整数 1 つ 1 つの値が大きいこと

です。

ここで $N$ が非常に小さいことに注目します。このような非常に小さい制約が与えられたとき、全探索解法がないかを検討するのは典型考察です。

するとこの問題は「いくつかの整数を選ぶ方法」さえ全列挙できれば解くことができます。 $N$ 個の整数の中からいくつかの整数を選ぶ方法は $2^N$ 通りありますが $N \leq 16$ なので多くても $2^{16} = 65536$ 通りしかないです。

よって、この問題は整数の選び方を表した 10 進数 $0,1,2,…,2^N-1$ を bit 全探索することで時間に余裕を持って求めることができます。実装については

bit 全探索の実装の方針のように、bit 全探索でいくつかの整数を選ぶ方法を全探索する
選んだ整数の総和を求めて、その値が $V$ になるのかを判定する

の 2 ステップでこの問題を解くことができます。

※動的計画法(DP)をご存知の方であればこの問題も DP で解けることが分かると思いますが、計算量が $O(NV)$ となるため実行時間に間に合いません。(また、配列の要素数が最大で $10^9$ を超えるので MLE(メモリ制限超過)や RE(実行時エラー)が発生します。)

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

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

    // bit全探索で部分和を全て求める
    bool flag = false;  // 可能かどうかを管理する変数flag
    for (int bit = 0; bit < (1 << N); bit++) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if ((bit >> i) & 1) {  // もしi番目を選んだなら
                sum += A[i];       // sumにA[i]を足す
            }
        }

        // 部分和とVが等しいか判定
        if (sum == V) flag = true;
    }

    // 出力
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

例題 2 の実装では、数字の「いくつか選ぶ方法」の配列 S を作成していましたが、実際の問題では配列 S を作成することはほとんどありません。その代わりに

$0 \leq i < N$ を満たす $i$ について、 $i$ 番目のものが $\text{bit}$ に含まれているなら、
それに応じた処理をその場で行う

場合がほとんどです。今回の部分和問題では

$i$ 番目のものを選んだかどうかを判定する
選んだなら変数sumに足す

を同時に行う実装をしています。

ABC289 C - Coverage

https://atcoder.jp/contests/abc289/tasks/abc289_c

【問題】
$1$ 以上 $N$ 以下の整数からなる集合が $M$ 個あり、 $S_1, S_2, \dots ,S_{M}$ と呼びます。
$S_i$ は $C_i$ 個の整数 $a_{i, 1}, a_{i, 2}, \dots ,a_{i, C_i}$ からなります。

$M$ 個の集合から $1$ 個以上の集合を選ぶ方法は $2^M - 1$ 通りあります。
このうち、次の条件を満たす選び方は何通りありますか？
$1 \leq x \leq N$ を満たす全ての整数 $x$ に対して、選んだ集合の中に $x$ を含む集合が少なくとも $1$ 個存在する。
【制約】
$1\leq N\leq 10$
$1\leq M\leq 10$
$1\leq C_i\leq N$
$1\leq a_{i, 1}< a_{i, 2}<\dots< a_{i, C_i}\leq N$

まさか bit 全探索が灰 diff になるとは。。。と思いました。

解法

問題文に「 $M$ 個の集合から $1$ 個以上の集合を選ぶ方法は $2^M - 1$ 通りあります」とご丁寧に書いてあるので、まず初めに $2^M$ 通りを全探索する bit 全探索ができないかを検討してみます。
ここで $M$ の制約を見ると $M\leq 10$ と 非常に小さい ため、多くても $2^{10} = 1024$ 通りしかないです。

よって、この問題は集合の選び方を表した 10 進数 $0,1,2,…,2^M-1$ を bit 全探索することで時間に余裕を持って求めることができることが分かります。

bit 全探索することは分かりましたが、問題文の条件である

$1 \leq x \leq N$ を満たす全ての整数 $x$ に対して、選んだ集合の中に $x$ を含む集合が少なくとも $1$ 個存在する

ことを判定するにはどうすれば良いでしょうか。
この判定は set と呼ばれる重複を取り除いてくれるデータ構造を用いることで

空のsetを用意する
選んだ集合に含まれている整数を全て set に挿入する
挿入した後、 set に $1, 2, \dots ,N$ が存在するかを判定する $\Leftrightarrow$ set の要素数が $N$ 個かどうかを判定する

ことで条件の判定を行うことができます。 set は C 問題以降で頻出なデータ構造になっていますので、この機会に是非覚えておきましょう。( set についての詳細は APG4b のAA - 3.03.STL のコンテナ内の細かい話欄を見てください。)

以上よりこの問題は

bit 全探索で $M$ 個の集合から $1$ 個以上の集合を選ぶ方法を全探索する
選んだ集合が問題文の条件を満たすかを set を使って判定する
条件を満たす集合の選び方を数えて、その数を出力する

ことで解くことができます！

計算量についてですが、set の 1 回の挿入には $O(\log N)$ の計算量が必要ですので、1 つの集合の挿入には $O(N\log N)$ 必要になります。よって最終的な計算量は $O(2^MNM\log N)$ となります。

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, M;
    cin >> N >> M;
    vector<int> C(M);
    vector<vector<int>> A(M);
    for (int i = 0; i < M; i++) {
        cin >> C[i];
        A[i].resize(C[i]);  // A[i]の長さをC[i]に変える
        for (int j = 0; j < C[i]; j++) cin >> A[i][j];
    }

    // bit全探索で条件を満たす集合の選び方がいくつあるかを求める
    int ans = 0;  // 何通りの選び方があるかを管理する変数ans
    for (int bit = 0; bit < (1 << M); bit++) {
        // 空のsetを用意する
        set<int> st;
        for (int i = 0; i < M; i++) {
            if ((bit >> i) & 1) {  // もしi番目の集合を選んだなら
                for (int j = 0; j < C[i]; j++) {
                    st.insert(A[i][j]);  // i番目の集合の整数を全てsetに挿入する
                }
            }
        }

        // setに1, 2, ..., Nが存在するかを判定
        if (st.size() == N) ans++;
    }

    // 出力
    cout << ans << endl;
}

ABC264 C - Matrix Reducing

https://atcoder.jp/contests/abc264/tasks/abc264_c

【問題】
$H_1$ 行 $W_1$ 列の行列 $A$ と、 $H_2$ 行 $W_2$ 列の行列 $B$ が与えられます。
$1 \leq i \leq H_1$ かつ $1 \leq j \leq W_1$ を満たす整数の組 $(i, j)$ について、行列 $A$ の $i$ 行目 $j$ 列目の要素は $A_{i, j}$ です。
$1 \leq i \leq H_2$ かつ $1 \leq j \leq W_2$ を満たす整数の組 $(i, j)$ について、行列 $B$ の $i$ 行目 $j$ 列目の要素は $B_{i, j}$ です。
行列 $A$ に対して、下記の $2$ つの操作のうちどちらかを行うことを、好きなだけ（ $0$ 回でも良い）繰り返すことができます。
$A$ の行を任意に $1$ つ選んで削除する。
$A$ の列を任意に $1$ つ選んで削除する。
行列 $A$ を行列 $B$ に一致させることができるかどうかを判定して下さい。
【制約】
$1\leq H_2\leq H_1\leq 10$
$1\leq W_2\leq W_1\leq 10$
$1\leq A_{i, j} \leq 10^9$
$1\leq B_{i, j} \leq 10^9$

解法

そろそろ勘の鋭い方であれば気づいたと思いますが、bit 全探索を使える場面は

非常に小さい制約が与えられたとき

であることが分かります。その上で、肝心なのは

「どこを決めれば全体が決まるか」という視点を忘れずに考察する
bit 全探索 - けんちょんの競プロ精進記録より

ということをよく考えることです。今回の問題では、 $H_1, H_2, W_1, W_2$ が全て小さい制約となっています。それでは、この制約を全探索することによって、全ての状態を全探索できるのかを考えていきます。

この問題では 2 種類の操作

$A$ の行を任意に $1$ つ選んで削除する。
$A$ の列を任意に $1$ つ選んで削除する。

を好きなだけ行うことができますが、要するにこれは

$H_1$ 個ある $A$ の行をいくつか選んで同時に削除する。
$W_1$ 個ある $A$ の列をいくつか選んで同時に削除する。

であることと同じであることが分かります。すなわち、 1 つずつ行と列を削除しても、同時に複数の行と列を削除しても最終的な状態は変化しないのです。 例えば、入力例 1 で

2 列目(元の行列の 2 列目)を削除 → 3 行目(元の行列の 3 行目)を削除 → 1 行目(元の行列の 1 行目)を削除 → 4 列目(元の行列の 5 列目)
1 行目、3 行目、2 列目、5 列目を同時に削除

とそれぞれ $A$ に操作を行うと以下のように状態が変化します。

2 列目(元の行列の 2 列目)を削除 → 3 行目(元の行列の 3 行目)を削除 → 1 行目(元の行列の 1 行目)を削除 → 4 列目(元の行列の 5 列目)を削除した場合

1 行目、3 行目、2 列目、5 列目を同時に削除した場合

どちらも最終的な $A$ の状態は同じであることが分かります。

さて、

$H_1$ 個あるものをいくつか選ぶ方法を全探索する
$W_1$ 個あるものをいくつか選ぶ方法を全探索する

を行うにはどうすればよかったのでしょうか。$H_1$ 個あるものをいくつか選ぶ方法は $2^{H_1}$ 通り、$W_1$ 個あるものをいくつか選ぶ方法は $2^{W_1}$ 通りあるので、、、そうです。bit 全探索を使って全ての方法である $2^{(H_1+W_1)}$ 通りを全列挙することができます。この組合せは最大でも $2^{(10+10)} = 1048576 \approx 10^6$ 通りなので全探索可能な範囲です。

今回は行の選び方を表した 10 進数 $0,1,2,…,2^{H_1}-1$ を bit 全探索するループと列の選び方を表した整と 10 進数 $0,1,2,…,2^{W_1}-1$ を bit 全探索するループの 2 重ループをすることで全探索することができます。

実装ですが少し量が多いので一つ一つ落ち着いてコードを書いていきましょう。大まかなステップとしては

$A$ のどの行を選んで残すのかを bit 全探索 + $A$ のどの列を選んで残すのかを bit 全探索する(2 重ループ)
行と列の bit を復元して、実際に操作を行った行列 $A’$ を構築する
$A’$ と $B$ が同じかどうかを判定する

の 3 ステップです。

まず、残す行の bit 全探索と残す列の bit 全探索を 2 重ループを書くと以下のようになります。

1
2
3
4
5
6
7
8
// A のどの行を残すかをbit全探索
for (int bit1 = 0; bit1 < (1 << H1); bit1++) {
    // A のどの列を残すかをbit全探索
    for (int bit2 = 0; bit2 < (1 << W1); bit2++) {
        /* 行、列のbitを復元して、実際に操作を行った行列 A' を構築する */
        /* A' と B が同じかどうかを判定する */
    }
}

次に実際に操作を行った行列を構築しますが、残す行の番号と残す列の番号をそれぞれ nh, nw という配列に格納して、それに従って $A’$ を構築します。
この際の注意点として先に

$A’$ と $B$ の行と列の大きさが等しい

ことを判定しないと、構築する際に配列外参照してしまう可能性があるので注意しましょう。この判定方法は、nh.size() と $H_2$ 、 nw.size() と $W_2$ が等しいか判定する方法か、bit の 1 の個数を返す __builtin_popcount(bit) を利用する方法の 2 つあります。

1
2
// nh の大きさと H_2, nw の大きさと W_2 が等しいか判定する
if((int)nh.size() != H2 || (int)nw.size() != W2) continue;

1
2
// __builtin_popcount(bit) を利用する
if(__builtin_popcount(bit1) != H2 || __builtin_popcount(bit2) != W2) continue;

実際に $A’$ を構築するとこのようなコードになります。( $A’$ は A_new という配列名にしています。)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 行、列のbitを復元して、実際に操作を行った行列 A' を構築する */

// nh := 残す行の番号を格納する配列
// nw := 残す列の番号を格納する配列
vector<int> nh, nw;
for (int i = 0; i < H1; i++) {
    if ((bit1 >> i) & 1) {  // もし i 番目の行を選んだなら
        nh.push_back(i);    // nh に番号を入れておく
    }
}
for (int j = 0; j < W1; j++) {
    if ((bit2 >> j) & 1) {  // もし j 番目の列を選んだなら
        nw.push_back(j);    // nw に番号を入れておく
    }
}

// nh の大きさと H_2, nw の大きさと W_2 が等しいか判定する
if ((int)nh.size() != H2 || (int)nw.size() != W2) continue;

// 実際に操作を行った行列 A' を構築する
vector A_new(H2, vector<int>(W2));
for (int i = 0; i < H2; i++) {
    for (int j = 0; j < W2; j++) {
        A_new[i][j] = A[nh[i]][nw[j]];
    }
}

以上を踏まえて、実装を行ってみましょう。このように重めの実装の際は、なるべく小さなステップに分割して考えることで実装しやすくなります。まさに「困難は分割せよ」です。計算量は $O(2^{(H_1+W_1)}H_1W_1)$ となります。

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int H1, W1, H2, W2;
    cin >> H1 >> W1;
    vector A(H1, vector<int>(W1));
    for (int i = 0; i < H1; i++) {
        for (int j = 0; j < W1; j++) {
            cin >> A[i][j];
        }
    }

    cin >> H2 >> W2;
    vector B(H2, vector<int>(W2));
    for (int i = 0; i < H2; i++) {
        for (int j = 0; j < W2; j++) {
            cin >> B[i][j];
        }
    }

    bool flag = false;  // 可能かどうかを管理する変数flag
    // A のどの行を残すかをbit全探索
    for (int bit1 = 0; bit1 < (1 << H1); bit1++) {
        // A のどの列を残すかをbit全探索
        for (int bit2 = 0; bit2 < (1 << W1); bit2++) {
            // nh := 残す行の番号を格納する配列
            // nw := 残す列の番号を格納する配列
            vector<int> nh, nw;
            for (int i = 0; i < H1; i++) {
                if ((bit1 >> i) & 1) {  // もし i 番目の行を選んだなら
                    nh.push_back(i);    // nh に番号を入れておく
                }
            }
            for (int j = 0; j < W1; j++) {
                if ((bit2 >> j) & 1) {  // もし j 番目の列を選んだなら
                    nw.push_back(j);    // nw に番号を入れておく
                }
            }

            // nh の大きさと H_2, nw の大きさと W_2 が等しいか判定する
            if ((int)nh.size() != H2 || (int)nw.size() != W2) continue;

            // 実際に操作を行った行列 A' を構築する
            vector A_new(H2, vector<int>(W2));
            for (int i = 0; i < H2; i++) {
                for (int j = 0; j < W2; j++) {
                    A_new[i][j] = A[nh[i]][nw[j]];
                }
            }

            // A' と B が同じかどうかを判定する
            if (A_new == B) flag = true;
        }
    }

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

さいごに

初めてで拙い文章になってしまいましたが、この記事で 1 人でも bit 全探索の理解に繋がったのであれば嬉しいです。参考文献の記事も僕自身が学習する際に読んでいたものであり、今回の記事を書く際にたくさん参考にさせてもらいました。是非、そちらの記事も確認してみてください。

練習問題

ビット演算 | アルゴ式 : ビットの説明から bit 全探索まで全てをカバーしている素晴らしい問題集です。
bit 全探索例題 : bit 全探索で解ける AtCoder の問題の簡易的な説明と実装コードです。

参考文献

$N$ 個の要素を持つ集合 $\{0, 1, 2, \dots, N-1\}$ の部分集合を全列挙することと同じ意味です。 ↩︎

＼シェアお願いします！／