C – Switches解説　AtCoder Beginner Contest 128解いてみた

Atcoder

Atcoder

こんにちは！seiです！
・Atcoderの解説を読んでもよくわからない…
・もっと詳しい解説が知りたい！

この記事は初心者向けにSwitchesを詳しく解説した記事です。
Atcoderを初めて16日が経過しました！

1 問題概要と制約条件の理解
2 Switchesの解答（C++）
3 解法のポイント
4 Switchesの計算量
5 AtCoder初心者が全探索問題に取り組む際の悩みと解決策
6 おわりに

問題概要と制約条件の理解

on と off の状態を持つ N 個のスイッチと、M 個の電球があります。スイッチには 1 から N の、電球には 1 から M の番号がついています。

電球 i は ki 個のスイッチに繋がっており、スイッチ si1,si2,…,sik のうち on になっているスイッチの個数を 2 で割った余りが pi に等しい時に点灯します。

全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるかという問題です。

制約条件は以下のとおりです。

1≤N,
M≤10
1≤ki≤N
1≤si,j≤N
pi は 0 または 1
入力は全て整数である

Switchesの解答（C++）

早速解答のコードです。

#include <bits/stdc++.h>

using namespace std;

int main()
{

    int n, m, k[11], s[11][11], p[11], result = 0;

    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> k[i];

        for (int j = 1; j <= k[i]; j++)
        {
            cin >> s[i][j];
        }
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> p[i];
    }

    // 各電球のスイッチの状態は要素数nの部分集合となっている。

    for (int msk = 0; msk < (1 << n); msk++)
    {

        int lightCount = 0;
        for (int i = 1; i <= m; i++)
        {
            int on = 0;
            for (int j = 1; j <= k[i]; j++)
            {
                if (msk & (1 << s[i][j] - 1))
                    on++;
            }
            if (on % 2 == p[i])
            {
                lightCount++;
            }
        }
        cout << endl;
        if (lightCount == m)
            result++;
    }

    cout << result << endl;

    return 0;
}

解法のポイント

bit全探索を使う
ある特定のスイッチの状態からの探索ではなく、あり得るすべてのスイッチの状態を全探索する

bit全探索を使えることに気づくことが重要です。このようにスイッチがn個あって({s1,s2~sn})、各スイッチの状態が部分集合になっているような場合({s1},{s2,s3})はbit全探索が使えます。ここでは、電球のスイッチの状態をbit列で表し、全探索することで解答しています。

point!：部分集合を全探索するときは、bit全探索を用いる

bit全探索を簡単に説明すると、例えば全部で4個のスイッチがあるとき(n=4)、

0000 (0)   -> すべての要素が選択されていない
0001 (1)   -> 最初の要素が選択されている
0010 (2)   -> 2 番目の要素が選択されている
0011 (3)   -> 最初と 2 番目の要素が選択されている
0100 (4)   -> 3 番目の要素が選択されている
...
1111 (15)  -> すべての要素が選択されている

上記のように「スイッチを選択している状態」と10進数の数字が一対一で対応します。
以下n=4の時で説明します。

for (int msk = 0; msk < (1 << n); msk++)

ここでは「スイッチを選択している状態」を全探索しています。
このforでは1を左に4ビットシフトした数、つまり2進数で10000、10進数だと2^4回forを回しています。

if (msk & (1 << s[i][j] - 1))

ここでは今調べているスイッチの状態（msk)とスイッチの番号を比べて、その番号のスイッチがONになっているかを調べています。-1することでシフト位置を調整しています。たとえばスイッチ2のときは1を左に1シフトするので0010となります。

そして、各電球について、その電球のスイッチがonである数が偶数か奇数かを判定し、その判定結果が要件を満たす場合には電球の個数を+1します。

全ての電球を探索し終わったときに、ONになっている電球の数が全ての電球と等しい際に答えを+1しています。

Switchesの計算量

Atcoderの制限時間では大体10^8~10^9が計算量の限界と言われています。
計算量を見積もるときは最大の計算量を考えないといけないので、N、Mが最大の10の時を考えます。
まずは普通に電球1~電球10までスイッチの状態を全探索する場合を考えてみます。
各電球のスイッチは最大で10個なので、電球1のスイッチの選び方(2^10通り)に対して電球2の選び方が2^10通りあります。電球10まであるので(2^10)^10となってしまい、計算が間に合わないことが分かります。

次に今回のbit全探索を使った実装は一番外側のforで2^10回次のforで10回その次のforで10回なので、2^10×10×10となります。ランダウ記号であらわすとO(2^n)となります。（係数と最大時数以外は無視）

for (int msk = 0; msk < (1 << n); msk++)
    {

        int lightCount = 0;
        for (int i = 1; i <= m; i++)
        {
            int on = 0;
            for (int j = 1; j <= k[i]; j++)
            {
                if (msk & (1 << s[i][j] - 1))
                    on++;
            }
            if (on % 2 == p[i])
            {
                lightCount++;
            }
        }
        cout << endl;
        if (lightCount == m)
            result++;
    }

AtCoder初心者が全探索問題に取り組む際の悩みと解決策

AtCoder初心者が全探索問題に取り組む際に悩むこととして、探索回数が膨大になることがあります。これを解決するために、以下のような工夫が有効です。

探索する対象の最適化
ビット演算を用いた高速化

探索対象の最適化は、探索する対象を工夫することで、探索回数を削減する方法です。ある問題で探索すべき項目が複数ある場合には、何をforで回すべきか考えると良いです。
例えば、以下の問題だと、A,Bのピザをforで回すのではなく、ABピザをforで回せばよいです。
https://atcoder.jp/contests/abc095/tasks/arc096_a

探索を工夫しても解けないようなときは、今回のようなビット全探索や、順列全探索などの知識が必要です。

おわりに

アルゴリズムの学習を始めて16日経過しましたが、日々実力がついてきているのを感じています。アルゴリズムの魅力は人間では量が多すぎて解けないような問題も短い時間で解くことができる、性質とデータ構造が同じであればどのような問題にも適用できるところだと思います。
今後も初心者なりにAtcoderを進めていく過程を発信していきます！