概要

ネットワーク内の端末のウイルス感染状況を、与えられた検査結果と矛盾しない範囲で最小の感染端末数で求める問題です。

考察

端末数 \(N\) が最大16と小さいため、すべての端末の感染状態の組み合わせ（\(2^N\) 通り）を全探索することが可能です。各組み合わせに対して、M個の検査結果と矛盾しないかチェックし、矛盾しない中で感染端末数が最小のものを選びます。素朴なアプローチでは全探索が可能なサイズなので、特に最適化なしでも十分高速に動作します。

アルゴリズム

ビット全探索を用います。端末の感染状態をNビットのビットマスクで表現し、0から\(2^N-1\)までのすべての状態を試します。各状態について、以下の手順で検査結果との整合性を確認します：

1. ビットマスクの立っているビット数を数え（これが感染端末数）、現在の最小値より大きければスキップ
2. 各検査について：
   • 検査対象端末のうち、少なくとも1台が感染している（ビットマスクで対応するビットが立っている）かチェック
   • 検査結果が「感染あり」(R_j=1)なのに感染端末が見つからない場合、または「感染なし」(R_j=0)なのに感染端末が見つかった場合、その状態は不適格
3. すべての検査を通過した状態の中で、最小の感染端末数を出力

計算量

• 時間計算量: \(O(M \cdot N \cdot 2^N)\)
• 空間計算量: \(O(M \cdot N)\)

実装のポイント

• ビットマスクの各ビットを端末番号に対応させる（端末iはビット位置i-1）

• 検査結果との整合性チェックでは、各検査対象端末集合を事前に保存しておき、ビット演算で効率的にチェック

• 現在の最小値より大きい感染端末数の状態は早期に枝刈りすることで、若干の効率化を図っている

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(0)
        return
        
    first_line = data[0].split()
    N = int(first_line[0])
    M = int(first_line[1])
    
    scans = []
    for i in range(1, M+1):
        parts = data[i].split()
        K_j = int(parts[0])
        S_list = list(map(int, parts[1:1+K_j]))
        R_j = int(parts[-1])
        scans.append((S_list, R_j))
    
    min_infected = float('inf')
    total_possible = 1 << N
    
    for mask in range(total_possible):
        valid = True
        count = bin(mask).count('1')
        if count >= min_infected:
            continue
            
        for S_list, R_j in scans:
            found = False
            for node in S_list:
                idx = node - 1
                if mask & (1 << idx):
                    found = True
                    break
                    
            if (R_j == 1 and not found) or (R_j == 0 and found):
                valid = False
                break
                
        if valid:
            if count < min_infected:
                min_infected = count
                
    print(min_infected)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。