【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【全探索：ビット全探索】

この記事は【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみたの子記事です。お読みになる前に親記事をご確認ください。

下記 $2$ つの記事の知識を前提として解説します。

ビット演算 (bit 演算) の使い方を総特集！〜マスクビットから bit DP まで〜の「6. bit 全探索」まで
bit 全探索 (1 の補足記事)

10. ALDS_5_A – 総当たり
11. AtCoder Beginner Contest 128 C – Switches
12. AtCoder Beginner Contest 002 D – 派閥
13. JOI 2008 予選 5 – おせんべい
14. Square869120Contest #4 B – Buildings are Colorful!

10. ALDS_5_A – 総当たり

問題へのリンク

ビット演算 (bit 演算) の使い方を総特集！〜マスクビットから bit DP まで〜の例題「部分和問題」の解法と同じ方法で基本的には解けます。
ただし、質問 (クエリ) が来るたびにビット全探索すると計算量が $\Omega(qn2^n) = 10^9$ 程度になり、実行時間制限に違反します。

実行時間制限違反例

そこで、バケットや set を用意して $A$ の要素の中のいくつかの要素を足しあわせてできる整数をすべて記録します。この場合、ビット全探索は一度しか行わないため、計算量はそれぞれ $O(n2^n + q) = 10^8$ 程度、 $O(n2^n + n q) = 10^8$ 程度となり、間に合います。

解答例 1

部分和問題は動的計画法を使って解くこともできます。基本的な解法は典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～の「問題 3:　部分和問題」にある通りです。
「問題 3:　部分和問題」の解法では $dp[i+1][j]$ を $0$ から $i$ 番目までの部分列の要素のうち、いくつかを足しあわせて $j$ とできるならば真、そうでないならば偽、となるように dp テーブルを更新します。その際、 $j$ についてのループは部分和の候補まで行います。本問題の場合、複数の候補 $m_i$ があるため、それらの最大値までが $j$ のループの範囲になります。
計算量は $O(n \max(m_i) + q) = 10^5$ 程度となり、ビット全探索に比べて高速に計算できます。

解答例 2
解答例 3 dp テーブルを使い回す実装です。

bitsetでの定数倍改善に記載のテクニックを使うとさらに高速な解答を作成できます。ただし、計算量のオーダーは前述の動的計画法と同じです。テクニックの概要は下記の通りです。

dp テーブルを bitset で保持します。
dp テーブルの更新をシフト演算子を用いて行います。

上記の解答例 3 では dp テーブルの更新を下記のように実装しました。

bool dp[2001] = {};
dp[0] = true;
for (int i = 0; i < n; ++i) {
    for (int j = max_m; j >= A_vec.at(i); --j)
        dp[j] |= dp[j - A_vec.at(i)];
}

dp をビット列だとみなすと、j についての for 文は「元の dp と dp を左に A_vec.at(i) だけずらしたビット列の和をとる」処理になっています。そのため、dp テーブルを bool 型の配列から bitset に変更すると、j についての for 文を使わずに下記のように実装できます。

bitset<2001> dp(1)
for (int i = 0; i < n; ++i) {
    dp |= (dp << A_vec.at(i))
}

解答例 4

11. AtCoder Beginner Contest 128 C – Switches

問題へのリンク

$N$ 個のスイッチの on/off をビット列で表現します。

bitset<10> switches;

各場合ごとに点灯した電球の個数を計算し、すべての電球が点灯した場合を数えます。
各電球に繋がっているスイッチもビット列で管理し、全体としては bitset の vector で管理します。

vector<int> p_vec(M);
vector<bitset<10>> connected(M, 0);
int k, s;
for (int i = 0; i < M; ++i) {
    cin >> k;
    for (int j = 0; j < k; ++j) {
        cin >> s;
        --s;
        connected.at(i).set(s);
    }
}
for (int i = 0; i < M; ++i)
    cin >> p_vec.at(i);

点灯した電球の個数は下記の関数で計算できます。各電球に繋がったスイッチのうち、状態が on であるスイッチの個数は & 演算子を使って計算できます。

int count_lighting_bulb(int M, const vector<int> &p_vec, 
        const vector<bitset<10>> &connected, const bitset<10> &switches)
{
    int cnt = 0;
    for (int i = 0; i < M; ++i) {
        int num_valid_switches = (connected.at(i) & switches).count();
        if (num_valid_switches % 2 == p_vec.at(i))
            ++cnt;
    }
    return cnt;
}

ビット列の長さが $N$ 以上であることが必須のため、上記の関数の計算量は $O(MN)$ です。
スイッチの on/off の場合ごとに上記の関数が呼び出されることから、全体の計算量としては $O(NM 2^N) = 10^5$ 程度で間に合います。

解答例

12. AtCoder Beginner Contest 002 D – 派閥

問題へのリンク

以下のように派閥の候補と人間関係を表します。

表現するもの	データ構造
派閥の候補	派閥に属する人のビットを $1$ とする長さ $N$ 以上のビット列
各議員の人間関係	知り合いのビットを $1$ とする長さ $N$ 以上のビット列 (自分も知り合いとする)
議員全体の人間関係	各議員の人間関係の vector

$N \leq 12$ であることを踏まえ、派閥の候補と議員全体の人間関係を次のように実装します。

bitset<12> choice; // 派閥の候補
vector<bitset<12>> acquaintances; // 議員全体の人間関係

派閥に含まれるすべての議員が互いに知り合いであるとは、次のように言い換えられます。

派閥内の任意の議員 $x$ に対し、派閥は $x$ の人間関係の部分集合である。

集合 $S$ が集合 $T$ の部分集合であるかの判定は $S \cap T = S$ の真偽でできます。これを上記の派閥と人間関係の実装に対して記述すると下記のようになります。

(choice & acquaintances.at(x)) == choice;

上記の判定を派閥に属する任意の議員に対し実行すれば、派閥が成立するか否かの判定ができます。実装は下記の関数のようになります。

bool is_group(int N, const vector<bitset<12>> &acquaintances,
        const bitset<12> &choice)
{
    for (int i = 0; i < N; ++i) {
        if (choice.test(i) == 0)
            continue;
        if ((choice & acquaintances.at(i)) != choice)
            return false;
    }
    return true;
}

派閥の候補をすべて列挙し、派閥が成立するときに派閥の人数を数えて、最大値を求めると解答となります。計算量は $O(N^2 2^N) = 10^6$ 程度です。

解答例

13. JOI 2008 予選 5 – おせんべい

問題へのリンク

問題文記載のヒントに着目します。

$R$ の上限 $10$ は $C$ の上限 $10000$ に比べて小さいことに注意せよ．

$R$ の上限が $10$ であるため、どの行を裏返すかはビット全探索しても $O(2^R) = 10^3$ 程度と問題なさそうです。
裏返す横の行を固定した後、できる限り多くの煎餅を出荷できるように裏返す縦の列を選ぶことを考えます。互いの列の裏返す・裏返さないはお互いに影響を与えないため、一列ずつ下記の場合分けを行えば良いです。

表を焼いている煎餅の枚数が裏を焼いている煎餅の枚数以下の場合は裏返さない。
表を焼いている煎餅の枚数が裏を焼いている煎餅の枚数より多い場合は裏返す。

上記の場合分けをしながら、煎餅の枚数を数える処理の計算量は $O(CR)$ です。
全体の計算量は $O(CR 2^R) = 10^8$ 程度です。実行時間制限は $10$ 秒のため、間に合います。
本当に裏返す (入力情報を書き換える) と次の探索の時に不便であるため、実際は行の裏返しの情報である長さ $R$ 以上のビット列 bit と煎餅の状態である二次元配列 grid の値を確認しながら、表を焼いている煎餅の枚数を数えます。

int cnt_j = 0; // j 列の表を焼いている煎餅の枚数
for (int k = 0; k < R; ++k) {
    // k 行を裏返した場合
    if (bit.test(k) == 1 && grid[k][j] == 0)
        ++cnt_j;
    // k 行を裏返さない場合
    if (bit.test(k) == 0 && grid[k][j] == 1)
        ++cnt_j;
}

解答例 1

JOI の解説にあるように、grid を各要素が $1$ 列の煎餅の状態を表すビット列の vector に変更すると、裏返す行を決めた後の表を焼いている煎餅の枚数は排他的論理和を使って下記の一行で計算できます。

int cnt_j = (bit ^ grid.at(j)).count();

解答例 2

14. Square869120Contest #4 B – Buildings are Colorful!

問題へのリンク

左から見えるようにする $K$ 個の建物の組み合わせをビット全探索で列挙します。
$N$ 個の建物のうち、どの建物の高さを増やすか考えます。高さは増やすことしかできず、見える予定のない建物の高さを増やしても仕方がありません。高さを増やす建物の候補は見えるようにする $K$ 個の建物に絞られます。
決められた $K$ 個の建物を見えるようにするには以下の処理を左から順に行えばできます。

左から第 $i$ 番目にある、見える予定の建物の高さと、第 $1$ 番目から第 $i - 1$ 番目までの建物の高さの最大値を比較する。
第 $i$ 番目の建物の方が真に高い場合は何もしない。
第 $i$ 番目の建物の方が低い場合は第 $1$ 番目から第 $i - 1$ 番目までの建物の高さの最大値より $1$ つ高くなるまで高さを増やす。

上記の処理を行い、高さを増すために払った金額を計算し、最小値を取れば必要な金額が求まります。
上記の処理は $1$ 番目から $i$ 番目までの建物の最大値を毎回更新して保持すれば $O(N)$ で計算できるため、全体の計算量は $O(N 2^N) = 10^6$ 程度で実行時間制限に違反せずに解答できます。

解答例 1