概要

\(N\) 台の端末（\(N \leq 16\)）の中から、\(M\) 個のセキュリティスキャン結果すべてと矛盾しない感染端末の組み合わせを求め、感染端末数が最小となるものを見つける問題です。本質的には最小集合被覆問題（Set Cover）をビットマスクで全探索する問題です。

考察

問題の整理

各端末を「感染している(1)」か「感染していない(0)」かで表すと、感染端末の集合は \(\{1, 2, \ldots, N\}\) の部分集合です。スキャン結果との整合性は以下の2種類の制約になります。

• \(R_j = 0\)（感染なし）: スキャン対象の端末はすべて感染していない。つまり対象端末は感染候補から除外される。
• \(R_j = 1\)（感染あり）: スキャン対象の端末の中に少なくとも1台は感染端末がある。

重要な気づき

1. \(R_j = 0\) の制約は簡単に処理できる: 「感染なし」と判定された端末集合に含まれる端末は、絶対に感染していません。これらを「禁止端末」としてまとめて除外できます。

2. \(R_j = 1\) の制約はヒッティングセット問題: 残った候補端末の中から、すべての「感染あり」スキャンの対象集合と少なくとも1つ共通要素を持つような最小部分集合を求める問題になります。これは集合被覆問題と等価で NP 困難ですが、\(N \leq 16\) なので全探索が可能です。

素朴なアプローチ

\(2^N\) 通りの部分集合をすべて試すと、\(N = 16\) のとき最大 \(2^{16} = 65536\) 通りです。各部分集合に対して \(M\) 個の制約をチェックしても \(65536 \times 100 \approx 6.5 \times 10^6\) 程度の計算量で十分高速です。

アルゴリズム

1. ビットマスクで表現: 端末 \(i\) をビット \(i-1\) に対応させ、各スキャンの対象端末集合をビットマスク化する。

2. 禁止端末の計算: \(R_j = 0\) のスキャンすべてについて対象端末のビットを OR で集約し、forbidden マスクを作る。感染候補（allowed）はその補集合。

3. \(R_j = 1\) の制約収集: 各「感染あり」スキャンの対象マスクを allowed で AND した結果を positive_masks リストに格納する。

4. 全列挙: allowed の部分集合をすべて列挙する。各部分集合 \(s\) について、すべての positive_masks に対して \((s \mathbin{\&} pm) \neq 0\) が成り立つか確認し、成り立つならビット数（popcount）を記録して最小値を更新する。

   • 部分集合の列挙には s = (s - 1) & allowed というテクニックを使い、allowed の部分集合だけを効率よく巡回する。

5. 最小値を出力。

具体例

\(N=4\), スキャン結果が「端末{1,2}に感染あり」「端末{3,4}に感染なし」の場合： - forbidden = {3,4} → allowed = {1,2} - positive_masks = [{1,2}] - allowed の部分集合: \(\{1,2\}, \{1\}, \{2\}, \emptyset\) - \(\{1\}\) で制約を満たし、\(|\{1\}| = 1\) → 答えは 1

計算量

• 時間計算量: \(O(2^N \times M)\)（allowed の部分集合数は最大 \(2^N\)、各部分集合に対して \(M\) 個の制約をチェック）
• 空間計算量: \(O(M)\)（スキャン情報の保持）

\(N \leq 16, M \leq 100\) なので \(2^{16} \times 100 \approx 6.5 \times 10^6\) で十分高速です。

実装のポイント

• ビットマスクによる集合演算: 端末集合をビットマスクで表現することで、AND/OR 演算だけで「共通要素があるか」「除外処理」が \(O(1)\) で行える。

• 部分集合列挙テクニック: s = (s - 1) & allowed で allowed の部分集合だけを降順に列挙できる。\(0\) も含めて漏れなく列挙するため、ループ末尾で s == 0 を判定して終了する。

• \(R_j = 0\) の前処理: 先に禁止端末を除外しておくことで、探索空間を大幅に削減できる（例: 半数の端末が禁止なら \(2^{N/2}\) に減少）。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    scans = []
    for j in range(M):
        K = int(input_data[idx]); idx += 1
        mask = 0
        for k in range(K):
            s = int(input_data[idx]); idx += 1
            mask |= (1 << (s - 1))
        R = int(input_data[idx]); idx += 1
        scans.append((mask, R))
    
    # We need to find minimum popcount subset of {0..N-1} (as bitmask) such that:
    # For each scan (mask, R):
    #   if R == 1: (subset & mask) != 0  (at least one infected in the scan set)
    #   if R == 0: (subset & mask) == 0  (no infected in the scan set)
    
    # First, for R==0 scans, no terminal in that scan set can be infected.
    # So we can compute a "forbidden" mask of terminals that must NOT be infected.
    forbidden = 0
    for mask, R in scans:
        if R == 0:
            forbidden |= mask
    
    # Allowed terminals (candidates for infection)
    allowed = ((1 << N) - 1) & ~forbidden
    
    # For R==1 scans, we need (subset & mask) != 0
    # Since subset is a subset of allowed, the effective constraint is (subset & (mask & allowed)) != 0
    # Collect the R==1 constraints
    positive_masks = []
    for mask, R in scans:
        if R == 1:
            effective = mask & allowed
            # effective must be non-zero (guaranteed by problem: a valid assignment exists)
            positive_masks.append(effective)
    
    # Now we need to find minimum size subset of 'allowed' bits that hits all positive_masks
    # This is a set cover problem. N <= 20, number of allowed bits <= 20.
    # Number of positive constraints <= 100.
    
    # We can use BFS over bitmasks ordered by popcount, or iterate by popcount.
    # But 2^20 = ~1M, and for each we check up to 100 constraints. That's ~100M which might be tight.
    # Let's optimize: precompute and check.
    
    # Actually, let's just enumerate subsets of 'allowed' in order of popcount.
    # We can do BFS by popcount or just iterate all subsets.
    
    # With N=20, 2^20 = 1048576. For each subset that is a subset of 'allowed',
    # we check all positive_masks. Let's do it.
    
    # To enumerate only subsets of 'allowed', we can use the subset enumeration trick.
    # Number of subsets of 'allowed' = 2^(popcount(allowed)) which is at most 2^20.
    
    # We want minimum popcount. Let's iterate all subsets of allowed and find the one
    # with minimum popcount that satisfies all constraints.
    
    # Optimization: iterate by popcount (0, 1, 2, ...) and return as soon as we find a valid one.
    
    if not positive_masks:
        print(0)
        return
    
    # Enumerate subsets of 'allowed' by increasing popcount
    # Use the submask enumeration: s = allowed, then (s-1) & allowed, etc.
    # But this doesn't go in popcount order.
    
    # Alternative: just check all 2^20 subsets. With bit operations this should be fast enough.
    
    best = N
    
    # Iterate all subsets of 'allowed'
    # Submask enumeration
    s = allowed
    while True:
        # Check if s satisfies all positive constraints
        valid = True
        for pm in positive_masks:
            if (s & pm) == 0:
                valid = False
                break
        if valid:
            pc = bin(s).count('1')
            if pc < best:
                best = pc
                if best == 0:
                    break
        if s == 0:
            break
        s = (s - 1) & allowed
    
    print(best)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。