概要

各端末が「感染している／していない」のどちらかだとして、スキャン結果（集合に感染端末が1台でもいれば1、いなければ0）と矛盾しない割り当てのうち、感染端末数が最小のものを求めます。

考察

この問題は、端末集合に対する条件がすべて 「集合と感染集合の交差が空かどうか」 で表せるのがポイントです。

• スキャン結果が \(R_j = 0\)（感染なし）
  → そのスキャンで調べた集合 \(S_j\) には感染端末が 1台もいない
  → 感染集合 \(X\) に対して \(X \cap S_j = \emptyset\)
  → つまり \(S_j\) に含まれる端末はすべて非感染で確定 します。

• スキャン結果が \(R_j = 1\)（感染あり）
  → その集合 \(S_j\) の中に感染端末が 少なくとも1台いる
  → \(X \cap S_j \neq \emptyset\)

ここで制約が \(N \le 16\) と小さいため、感染端末集合 \(X\) を 全探索（\(2^N\) 通り） できます。
素朴に「全探索して全条件チェック」でも間に合いますが、さらに速くするために次を行います：

1. \(R_j=0\) の条件はまとめて処理し、感染候補から即座に除外する（強力な枝刈り）
2. 現在の最小感染数（best）以上の候補は調べない（個数による枝刈り）
3. 集合は bitmask で持ち、交差判定を高速化する（x & mask）

アルゴリズム

bitmask を使い、感染端末集合 \(X\) を \(0\)〜\((1<<N)-1\) の整数で表します（\(i\) bit目が1なら端末 \(i\) が感染）。

1. 入力を読み、各スキャンの対象集合を bitmask mask に変換する。
2. \(R=0\) のスキャンについて：
   • その集合は感染者を含まないので、集合全体を must_zero に OR して蓄積する。
   • must_zero に立っているビットの端末は 感染にできない。
3. \(R=1\) のスキャンについて：
   • 条件「\(X \cap S_j \neq \emptyset\)」を満たす必要があるので、r1_masks に mask を保存する。
4. 全ての \(X\)（\(0 \le X < 2^N\)）を列挙し、以下を満たすもののうち感染数が最小のものを探す：
   • (X & must_zero) == 0（感染不可端末を感染にしていない）
   • すべての m in r1_masks について (X & m) != 0（各「感染あり」集合と交差する）

感染数は popcount（Pythonでは bit_count()）で数え、最小値を更新します。

計算量

• 時間計算量: \(O(2^N \cdot M)\)
  （\(N \le 16\) なので最大でも \(2^{16}=65536\) 通りを、各候補で最大 \(M\) 個チェック）
• 空間計算量: \(O(M)\)
  （\(R=1\) のスキャン集合を保存する分＋定数個の変数）

実装のポイント

• 端末番号は入力が \(1\) 始まりなので、bit 位置に合わせて -1 してから 1 << s を立てます。

• \(R=0\) の条件は must_zero にまとめると、列挙時に (X & must_zero) の1回判定で弾けて高速です。

• すでに見つけた最小値 best 以上の感染数の候補は不要なので、bit_count() 後に枝刈りします。

• 交差判定は X & mask が 0 かどうかを見るだけで済み、集合をリストで持つより大幅に高速です。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    must_zero = 0
    r1_masks = []

    for _ in range(M):
        K = next(it)
        mask = 0
        for _ in range(K):
            s = next(it) - 1
            mask |= 1 << s
        r = next(it)
        if r == 0:
            must_zero |= mask
        else:
            r1_masks.append(mask)

    best = N + 1
    for x in range(1 << N):
        if x & must_zero:
            continue
        bc = x.bit_count()
        if bc >= best:
            continue
        ok = True
        for m in r1_masks:
            if (x & m) == 0:
                ok = False
                break
        if ok:
            best = bc
            if best == 0:
                break

    print(best)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。