概要

\(N\) 個の消灯している電球に対し、指定された電球の点灯・消灯を反転させる \(M\) 個のスイッチがあります。いくつかのスイッチを押して、最終的に点灯している電球の数をちょうど \(K\) 個にするための「押すスイッチの最小個数」を求める問題です。

スイッチの数 \(M\) が最大で \(23\) と小さいため、半分全列挙（Meet-in-the-middle） を用いることで高速に解くことができます。

---

考察

1. 素直な全探索とその限界

各スイッチについて「押す」か「押さない」かの選択肢は \(2\) 通りあります。スイッチが \(M\) 個あるため、すべての組み合わせは \(2^M\) 通り存在します。 \(M \leq 23\) のとき、\(2^{23} \approx 8.4 \times 10^6\) 通りとなります。

C++などの高速な言語であれば \(2^{23}\) 通りの全探索も実行時間制限に間に合う可能性がありますが、Pythonなどのインタプリタ言語では、各状態で「電球の状態の計算」や「点灯している電球の数（ポップカウント）の計算」を行うと、定数倍の重さにより制限時間（通常2秒）を超過（TLE）してしまいます。

2. 半分全列挙による高速化

そこで、スイッチの集合を前半の \(M_1\) 個と後半の \(M_2\) 個に分割します。 - \(M_1 = \lfloor M/2 \rfloor\) （最大 \(11\)） - \(M_2 = M - M_1\) （最大 \(12\)）

このように分割すると、それぞれのグループにおけるスイッチの押し方の組み合わせは、高々 \(2^{11} = 2048\) 通り、および \(2^{12} = 4096\) 通りとなり、非常に小さな規模に抑えられます。

1. 前半の探索: 前半のスイッチの組み合わせによって作れる「電球の状態」と「その状態にするための最小のスイッチ数」をすべて求め、辞書に記録します。
2. 後半の探索: 同様に、後半のスイッチの組み合わせによって作れる「電球の状態」と「最小のスイッチ数」を辞書に記録します。
3. マージ（組み合わせ）: 前半の状態 \(s_1\)（スイッチ数 \(w_1\)）と、後半の状態 \(s_2\)（スイッチ数 \(w_2\)）を組み合わせたとき、最終的な電球の状態は \(s_1 \oplus s_2\) （\(\oplus\) は排他的論理和 XOR）となります。この合成された状態において、点灯している電球の数（ビットが立っている数）がちょうど \(K\) 個になるもののうち、\(w_1 + w_2\) が最小となるものを探します。

---

アルゴリズム

1. 電球状態のビット表現

\(N\) 個の電球の状態を、\(N\) 桁のビット列（整数）として表現します。 - \(i\) 番目の電球が点灯している \(\leftrightarrow\) 下から \(i\) 桁目のビットが 1 - \(i\) 番目の電球が消灯している \(\leftrightarrow\) 下から \(i\) 桁目のビットが 0

初期状態はすべての電球が消灯しているため、整数 0 です。各スイッチが影響する電球の情報をビットマスクとして事前に変換しておきます。スイッチを押す操作は、現在の状態とスイッチのマスクとの XOR（排他的論理和）演算 に対応します。

2. 前半・後半のDP（全列挙）

前半の \(M_1\) 個のスイッチについて、1つずつスイッチを追加しながら、作ることができる状態と最小の重み（押したスイッチの数）を更新していきます。 同様の処理を後半の \(M_2\) 個のスイッチに対しても行います。

3. ソートと枝刈りを用いたマージ

前半の結果を格納した dp1 と後半の結果を格納した dp2 を、それぞれ「スイッチの数（重み）」の昇順にソートします。

2つのリストから要素 \((s_1, w_1)\) と \((s_2, w_2)\) を取り出して組み合わせる際、以下の強力な枝刈り（探索の打ち切り）を適用します。 - すでに暫定の最小値 ans が見つかっているとき、 \(w_1 + w_2 \geq \text{ans}\) となる組み合わせについては、これ以上探索しても最小値を更新できないため、内側のループや外側のループを break してスキップします。

これにより、最悪計算量 \(O(2^{M_1} \times 2^{M_2}) = O(2^M)\) のマージ処理が、平均して極めて高速に終了します。

---

計算量

• 時間計算量: \(O(2^{M_1} + 2^{M_2} + \text{マージにかかる時間})\) 前半・後半の全列挙は \(2^{11} + 2^{12} = 6144\) 回のループで終わるため一瞬です。マージ処理は最悪 \(2^{23}\) 回のループになりますが、重みの昇順にソートして枝刈りを行うため、実質的な探索回数は非常に少なくなります（最悪ケースでも Python で数十ミリ秒〜数百ミリ秒で動作します）。
• 空間計算量: \(O(2^{M/2})\) 前半と後半の状態を保持する辞書のサイズは最大でも \(2^{12} = 4096\) であり、メモリはほぼ消費しません。

---

実装のポイント

ポップカウント（立っているビット数）の高速化

2つの状態を XOR 合成した値 xor_val = s1 ^ s2 の立っているビット数を数える必要があります。 Python の bin(x).count('1') は手軽ですが、ループ内で何度も呼び出すとボトルネックになります。

本コードでは、12ビット（\(0\) から \(4095\) まで）の数値に対するビット数をあらかじめ配列 pc にプリコンピュート（事前計算）しています。 \(N \leq 23\) であるため、23ビットの数値のポップカウントは、下位12ビットと上位11ビットに分割してテーブルを参照することで、以下のように定数時間 \(O(1)\) で高速に計算できます。

ones = pc[xor_val & 0xfff] + pc[xor_val >> 12]

ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    switches = []
    idx = 3
    for _ in range(M):
        c = int(data[idx])
        mask = 0
        for j in range(c):
            mask |= 1 << (int(data[idx + 1 + j]) - 1)
        switches.append(mask)
        idx += 1 + c
        
    M1 = M // 2
    M2 = M - M1
    
    dp1 = {0: 0}
    for j in range(M1):
        sw = switches[j]
        next_dp = dp1.copy()
        for state, w in dp1.items():
            ns = state ^ sw
            nw = w + 1
            if ns not in next_dp or nw < next_dp[ns]:
                next_dp[ns] = nw
        dp1 = next_dp

    dp2 = {0: 0}
    for j in range(M1, M):
        sw = switches[j]
        next_dp = dp2.copy()
        for state, w in dp2.items():
            ns = state ^ sw
            nw = w + 1
            if ns not in next_dp or nw < next_dp[ns]:
                next_dp[ns] = nw
        dp2 = next_dp

    pc = [0] * 4096
    for i in range(4096):
        pc[i] = pc[i >> 1] + (i & 1)

    list1 = sorted(dp1.items(), key=lambda x: x[1])
    list2 = sorted(dp2.items(), key=lambda x: x[1])

    ans = 1000
    for s1, w1 in list1:
        if w1 >= ans:
            break
        for s2, w2 in list2:
            if w1 + w2 >= ans:
                break
            xor_val = s1 ^ s2
            ones = pc[xor_val & 0xfff] + pc[xor_val >> 12]
            if ones == K:
                ans = w1 + w2
                
    if ans == 1000:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    solve()

---

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