概要

\(N\) 台の端末と \(M\) 回のスキャン結果が与えられたとき、すべてのスキャン結果と矛盾しないような「感染端末の組み合わせ」の中で、感染端末の台数が最小となるものを求める問題です。

考察

この問題は、以下の3つのステップで考えることができます。

1. 絶対に感染していない端末を特定する

スキャン結果が \(R_j = 0\)（感染なし）の場合、そのスキャン対象となった集合に含まれる端末はすべて「感染していない」ことが確定します。 まず、すべての \(R_j = 0\) のスキャンを確認し、一度でも「感染なし」の集合に含まれた端末を「クリーンな端末」としてマークします。

2. 「感染あり」のスキャン条件を整理する

次に、スキャン結果が \(R_j = 1\)（感染あり）の場合を考えます。 この条件は、「その集合の中に、少なくとも1台は感染端末がある」ことを意味します。 ここで、ステップ1で特定した「クリーンな端末」は、どの \(R_j = 1\) の集合に含まれていても「感染あり」の原因にはなり得ません。そのため、各 \(R_j = 1\) の集合からクリーンな端末を取り除いた「感染の可能性がある端末だけの集合」を改めて作ります。

3. 最小の端末数で条件を満たす（集合被覆問題）

残った課題は、「すべての \(R_j = 1\) の集合から、少なくとも1台ずつ端末を選び、選ぶ端末の総数を最小にする」ことです。 これは「集合被覆問題」と呼ばれる有名な問題の形をしていますが、今回の制約は \(N \leq 16\) と非常に小さいため、ビットを用いた全探索や動的計画法（DP）で十分に高速に解くことができます。

アルゴリズム

1. クリーン端末の除外: \(R_j = 0\) のスキャンに含まれる端末を列挙し、それ以外の端末（感染の可能性がある端末）を \(K\) 台特定します。
2. ターゲット集合の作成: \(R_j = 1\) の各スキャンについて、その中に含まれる「感染の可能性がある端末」の集合をビットマスクなどで管理します。
3. ビットDPによる最適化: 感染の可能性がある \(K\) 台の端末について、どの端末を選ぶかの組み合わせを \(2^K\) 通り探索します。
   • dp[mask] : 端末の選び方 mask（どの端末を感染させると仮定するか）によって、いくつの \(R_j = 1\) のスキャン条件が満たされるかを保持します。
   • すべてのスキャン条件（\(R_j = 1\) のものすべて）を満たす mask のうち、立っているビット（感染端末数）が最小のものを答えとします。

※正解コードでは、計算を効率化するために「ある端末の集合がどのスキャンをカバーするか」を DP で更新していく手法を取っています。

計算量

\(N\) を端末数、\(M\) をスキャン数とします。

• 時間計算量: \(O(MN + 2^N)\)
  • 入力の読み込みとクリーン端末の特定に \(O(MN)\)。
  • 感染の可能性がある端末の組み合わせの探索に \(O(2^N)\)。
  • \(N \leq 16\) なので、\(2^{16} = 65,536\) となり、制限時間内に余裕を持って動作します。
• 空間計算量: \(O(M + 2^N)\)
  • スキャン情報の保持と DP テーブルのサイズに依存します。

実装のポイント

• ビット演算の活用: 「どのスキャン条件が満たされたか」や「どの端末を選んだか」を整数のビット（\(0\) または \(1\)）で表現することで、集合の和集合（OR演算）や要素の判定を高速に行えます。

• 不要な条件の削減: あるスキャン \(A\) の対象端末が別のスキャン \(B\) の対象端末のサブセット（一部）である場合、スキャン \(A\) さえ満たせばスキャン \(B\) は自動的に満たされます。このような冗長なスキャン結果を事前に取り除くことで、定数倍の高速化が可能です（コード内の minimal_sets の処理）。

  ソースコード

import sys

def solve():
    # Read all input at once for faster processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of terminals, M: number of scans
    N = int(input_data[0])
    M = int(input_data[1])
    
    scans = []
    ptr = 2
    for _ in range(M):
        K_j = int(input_data[ptr])
        S_j = list(map(int, input_data[ptr+1 : ptr+1+K_j]))
        R_j = int(input_data[ptr+1+K_j])
        scans.append((S_j, R_j))
        ptr += 1 + K_j + 1
        
    # 1. Identify terminals that must be clean (R_j = 0 means no infected in that set)
    must_be_clean = [False] * (N + 1)
    for s_j, r_j in scans:
        if r_j == 0:
            for terminal in s_j:
                must_be_clean[terminal] = True
                
    # 2. Identify potential infected terminals (those not proven to be clean)
    possible_infected = []
    for i in range(1, N + 1):
        if not must_be_clean[i]:
            possible_infected.append(i)
            
    # 3. Identify scans that must have at least one infected terminal (R_j = 1)
    # For these scans, we only consider terminals that are not already proven clean.
    target_sets = []
    for s_j, r_j in scans:
        if r_j == 1:
            t_j = [t for t in s_j if not must_be_clean[t]]
            target_sets.append(set(t_j))
            
    # 4. If no R_j = 1 scans exist, the minimum number of infected terminals is 0.
    if not target_sets:
        print(0)
        return

    # 5. Optimization: Redundancy check for target_sets.
    # A scan is redundant if its set of possible infected terminals is a 
    # superset of another scan's set. Satisfying the subset satisfies the superset.
    target_sets.sort(key=len)
    minimal_sets = []
    for s in target_sets:
        for m in minimal_sets:
            if m.issubset(s):
                break
        else:
            minimal_sets.append(s)
    target_sets = minimal_sets
        
    K = len(possible_infected)
    M_prime = len(target_sets)
    
    # 6. For each potential infected terminal, create a bitmask of the scans it satisfies.
    # The j-th bit is 1 if terminal p satisfies the j-th minimal scan.
    satisfied_by_terminal = [0] * K
    for i, p in enumerate(possible_infected):
        for j, s in enumerate(target_sets):
            if p in s:
                satisfied_by_terminal[i] |= (1 << j)
    
    # Optimization: Filter out terminals that don't satisfy any remaining scan.
    satisfied_by_terminal = [x for x in satisfied_by_terminal if x > 0]
    K = len(satisfied_by_terminal)
    
    # target_all represents the bitmask where all minimal scans are satisfied.
    target_all = (1 << M_prime) - 1
    
    # 7. Use bitmask DP to find the minimum terminals needed to satisfy all scans.
    # dp[i] stores the union of scans satisfied by the subset of terminals represented by mask 'i'.
    # Since N <= 20, 2^N = 1,048,576 is small enough for this approach in Python.
    dp = [0] * (1 << K)
    ans = K
    
    for i in range(1, 1 << K):
        # Identify the lowest set bit to transition from a previously calculated state.
        lowbit = i & -i
        idx = lowbit.bit_length() - 1
        
        # Calculate scans satisfied by subset 'i' using the result of subset '(i without lowbit)'.
        val = dp[i ^ lowbit] | satisfied_by_terminal[idx]
        dp[i] = val
        
        # If the current subset satisfies all required scans, check its size.
        if val == target_all:
            cnt = bin(i).count('1')
            if cnt < ans:
                ans = cnt
    
    # Output the minimum number of infected terminals found.
    print(ans)

if __name__ == '__main__':
    solve()

---

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