概要

\(N\) 台の端末のうち、スキャン結果と矛盾しない最小の感染端末数を求める問題です。

考察

この問題では、各端末が「感染している」か「感染していない」かという二値の状態を持ちます。このような場合、全パターンを試すことを考えたくなります。端末の数 \(N\) は最大で \(16\) なので、全端末の感染状態をビット列で表現しても \(2^{16} = 65536\) 通りであり、十分に小さいため、全探索が可能です。

各スキャンは、「ある集合に感染端末が含まれているかどうか」を返すので、ある感染パターンに対して、そのスキャン結果と一致しているかを逐一確認することで、そのパターンが条件を満たすか判定できます。

素朴に全パターンを試して、それぞれについてすべてのスキャンと照らし合わせる方法は、計算量的にも現実的です。特に制約が緩いため、より複雑なアルゴリズムは必要ありません。

アルゴリズム

1. 各端末の感染状況をビットマスクで管理し、\(0\) から \(2^N - 1\) までのすべてのパターンを試す。
2. 各パターンに対応する感染端末の集合を構築する（例：ビット \(i\) が立っていれば端末 \(i+1\) が感染）。
3. 各スキャン結果とそのパターンが矛盾しないかを確認する：
   • スキャン対象に感染端末が含まれていれば結果は \(1\)
   • 含まれていなければ結果は \(0\)
4. 矛盾がなければ、そのパターンでの感染端末数を記録し、最小値を更新する。
5. 全パターンを調べ終えた後、最小の感染端末数を出力する。

計算量

• 時間計算量: \(O(2^N \cdot M \cdot N)\)
  • \(2^N\) 個のパターンに対して、\(M\) 個のスキャンを確認し、各スキャンで最大 \(N\) 個の端末を処理する。
• 空間計算量: \(O(M + N)\)
  • スキャン情報と感染端末の集合を保持するのに必要な領域。

実装のポイント

• 端末番号は1-indexedなので、ビット位置と対応させるときに注意（i + 1にするなど）。
• 各スキャンの判定部分で、集合の積（共通部分）を使って判定を行うとシンプルに書ける。
• set を使うことで、あるスキャンの対象に感染端末が含まれているかを効率よく判定できる。

## ソースコード

```python
def main():
    N, M = map(int, input().split())
    scans = []
    for _ in range(M):
        line = list(map(int, input().split()))
        K = line[0]
        S = line[1:K+1]
        R = line[K+1]
        scans.append((S, R))
    
    min_infected = N + 1
    
    # 全ての感染パターンを試す (2^N通り)
    for mask in range(1 << N):
        infected = set()
        for i in range(N):
            if mask & (1 << i):
                infected.add(i + 1)  # 端末番号は1-indexed
        
        # スキャン結果と矛盾がないかチェック
        valid = True
        for S, R in scans:
            intersect = infected & set(S)
            has_infected = len(intersect) > 0
            result = 1 if has_infected else 0
            if result != R:
                valid = False
                break
        
        if valid:
            min_infected = min(min_infected, len(infected))
    
    print(min_infected)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。