概要

\(N\) 個の電球と \(M\) 個のスイッチがあり、各スイッチを押すと対応する電球の ON/OFF が反転します。最終的に点灯している電球の数をちょうど \(K\) 個にするために、押す必要のあるスイッチの最小個数を求める問題です。

考察

1. 状態の表現と遷移

電球の ON/OFF 状態は、ビット（0 が消灯、1 が点灯）を用いて表現できます。 各スイッチが影響する電球の集合も、同様にビットマスク（どのビットが立っているか）で表すことができます。

ある電球の状態に対してスイッチを押す（状態を反転させる）という操作は、ビット演算の 排他的論理和（XOR, ^） に対応します。 例えば、現在の電球の状態を表すビット列を current_mask、押すスイッチのビットマスクを mask[idx] とすると、スイッチを押した後の状態は current_mask ^ mask[idx] と表せます。

2. 全探索の現実性

スイッチの数 \(M\) は最大で \(23\) です。 それぞれのスイッチについて「押す」「押さない」の 2 通りの選択肢があるため、すべての組み合わせは \(2^M\) 通り存在します。 \(M = 23\) のとき、 \(2^{23} \approx 8.4 \times 10^6\) （約840万）通りとなります。 これは、プログラムの実行制限時間（通常2秒）に対して十分に小さく、愚直にすべての組み合わせを探索しても間に合わせることができます。

3. 高速化（枝刈り）

さらに実行時間を短縮し、効率的に探索を行うために深さ優先探索（DFS）と枝刈りを組み合わせます。 具体的には、以下の工夫を行います。

• 暫定最小値による枝刈り: 探索の途中で、すでにこれまでに押したスイッチの数が「これまでに見つかった最適な答え（最小値）」以上になってしまった場合、その先を探索しても最適解が更新されることはありません。したがって、その時点で探索を打ち切ります。
• 「押さない」選択を優先する: スイッチを「押さない」場合を先に探索することで、押すスイッチの数が少ない状態を早い段階で探索できます。これにより、暫定の最小値が素早く小さな値に更新され、上記の枝刈りがより強力に機能するようになります。

---

アルゴリズム

1. 入力のビットマスク化: 各スイッチが影響する電球の情報を、0-indexed に変換した上でビットマスク（整数値）として保持します。
2. DFSによる全探索: 関数 dfs(idx, current_mask, switch_count) を用いて、 \(0\) 番目から \(M-1\) 番目のスイッチを順番に調べる再帰関数を定義します。
   • ベースケース:
     • switch_count がこれまでの暫定最小値 ans 以上なら、探索を打ち切る（枝刈り）。
     • すべてのスイッチの選択が終わったとき（idx == M）、現在の状態 current_mask において立っているビットの数（点灯している電球の数）が \(K\) と等しければ、ans を switch_count で更新する。
   • 遷移:
     • 現在のスイッチを「押さない」場合：dfs(idx + 1, current_mask, switch_count)
     • 現在のスイッチを「押す」場合：dfs(idx + 1, current_mask ^ mask[idx], switch_count + 1)
3. 答えの出力: 探索終了後、ans が初期値のままであれば達成不可能として -1 を出力し、そうでなければ ans を出力します。

---

計算量

• 時間計算量: 最悪 \(O(2^M)\) 最悪の場合でも状態数は \(2^{23} \approx 8.4 \times 10^6\) であり、各状態における遷移は \(O(1)\) のビット演算で行われるため、実行時間制限に余裕で間に合います。また、枝刈りによって実際の探索ノード数はこれよりも大幅に少なくなります。
• 空間計算量: \(O(M)\) 再帰呼び出しの深さは最大で \(M\) であり、システムスタックに消費されるメモリはごくわずかです。

---

実装のポイント

• std::popcount の利用: C++20 から導入された std::popcount（または __builtin_popcount）を使用することで、整数値の立っているビットの数（点灯している電球の数）を \(O(1)\) で高速にカウントできます。

• 1-indexed から 0-indexed への変換: 入力される電球の番号は \(1\) から \(N\) ですが、ビットシフト演算 (1U << s) を用いるために、電球の番号を \(0\) から \(N-1\) にデクリメントして処理しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <bit>

using namespace std;

int N, M, K;
vector<unsigned int> mask;
int ans = 1e9;

void dfs(int idx, unsigned int current_mask, int switch_count) {
    if (switch_count >= ans) return;
    if (idx == M) {
        if (std::popcount(current_mask) == K) {
            ans = min(ans, switch_count);
        }
        return;
    }
    // スイッチを押さない場合を先に探索（押す個数が少ない方を優先して枝刈りを効かせる）
    dfs(idx + 1, current_mask, switch_count);
    // スイッチを押す場合
    dfs(idx + 1, current_mask ^ mask[idx], switch_count + 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M >> K)) return 0;

    mask.resize(M, 0);
    for (int i = 0; i < M; ++i) {
        int c;
        cin >> c;
        for (int j = 0; j < c; ++j) {
            int s;
            cin >> s;
            --s;
            mask[i] |= (1U << s);
        }
    }

    dfs(0, 0, 0);

    if (ans > M) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。