概要

\(N\) 台のコンピュータをグループ分けし、各ウイルスの感染対象が同一グループに収まった場合のみ被害が発生するというルールの下で、被害を受けるコンピュータ台数を最小化する集合分割最適化問題です。

考察

重要な気づき

1. \(N \leq 15\) という制約: コンピュータ集合をビットマスクで表現でき、部分集合の列挙が現実的な計算量で可能です。

2. グループごとの被害は独立に計算可能: あるグループ \(G\) を1つのグループとした場合、\(G\) 内で発生する被害は「感染対象 \(S_j\) が \(G\) の部分集合であるようなウイルス \(j\) すべての \(S_j\) の和集合」です。

3. 集合分割問題への帰着: 全コンピュータの集合を互いに素なグループに分割し、各グループの被害の合計を最小化すればよいです。

素朴なアプローチの問題点

各グループ \(G\) に対して被害を計算するために全ウイルスを走査すると、\(O(2^N \cdot M)\) の前処理が必要になります。これでも \(N=15\) では動きますが、SOS DP を使うとより効率的かつエレガントに計算できます。

アルゴリズム

ステップ1: 各グループの被害コスト計算（SOS DP）

各ウイルスの感染対象 \(S_j\) をビットマスクで表現します。

まず、virus_or[mask] を「\(S_j\) がちょうど mask に等しいウイルスの \(S_j\) の OR」として初期化します（実質的に virus_or[mask] = mask if そのようなウイルスが存在）。

次に、SOS（Sum over Subsets）DP を行います：

\[\text{damage}[G] = \bigcup_{\text{T} \subseteq G} \text{virus\_or}[T]\]

これは各ビット \(i\) について damage[G] |= damage[G ^ (1 << i)]（\(G\) のビット \(i\) が立っている場合）と更新する \(O(N \cdot 2^N)\) の DP で計算できます。

damage[G] は「\(G\) が1つのグループを形成した場合に被害を受けるコンピュータのビットマスク」を表します。コスト cost[G] = popcount(damage[G]) です。

ステップ2: 集合分割 DP

\(\text{dp}[\text{mask}]\) を「ビットマスク mask で表されるコンピュータ集合を最適にグループ分けしたときの最小被害台数」とします。

遷移は：

\[\text{dp}[\text{mask}] = \min_{G \subseteq \text{mask}, G \neq \emptyset} \left( \text{cost}[G] + \text{dp}[\text{mask} \setminus G] \right)\]

mask の空でない部分集合 \(G\) をすべて列挙し、\(G\) を1つのグループにした場合のコストと残りの最適解の和の最小値を取ります。

答えは \(\text{dp}[(1 \ll N) - 1]\) です。

具体例

\(N=3\), ウイルスの感染対象が \(\{1,2\}\) と \(\{2,3\}\) の場合： - 全員を1グループにすると、両ウイルスが発動し被害は \(\{1,2,3\}\) で3台 - \(\{1,2\}\) と \(\{3\}\) に分けると、第1ウイルスが発動（被害2台）、第2ウイルスは阻止 - \(\{1\}\) と \(\{2,3\}\) に分けると、第2ウイルスが発動（被害2台）、第1ウイルスは阻止 - \(\{1\}\), \(\{2\}\), \(\{3\}\) に分けると、両ウイルスとも阻止され被害0台 → 最適

計算量

• 時間計算量: \(O(N \cdot 2^N + 3^N)\)
  • SOS DP: \(O(N \cdot 2^N)\)
  • 集合分割 DP（全部分集合の列挙）: \(O(3^N)\)（\(N=15\) で約 \(1.4 \times 10^7\)）
• 空間計算量: \(O(2^N)\)

実装のポイント

• ビットマスクによる集合表現: コンピュータ \(i\) を第 \((i-1)\) ビットに対応させ、集合演算をビット演算で高速に行います。

• 部分集合の列挙テクニック: sub = (sub - 1) & mask というイディオムで、mask の空でない部分集合を効率的に列挙できます。

• SOS DP の正当性: damage[G] は \(G\) の部分集合であるすべてのウイルスマスクの OR を計算しており、\(S_j \subseteq G\) となるウイルスの感染対象の和集合を正しく求めています。

• damage[G] は必ず G の部分集合: \(S_j \subseteq G\) のウイルスしか含まないため、damage[G] & G == damage[G] が常に成り立ち、グループ外への被害を心配する必要はありません。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    viruses = []
    for j in range(M):
        k = int(input_data[idx]); idx += 1
        mask = 0
        for i in range(k):
            s = int(input_data[idx]); idx += 1
            mask |= (1 << (s - 1))
        viruses.append(mask)
    
    # For each subset of computers (as bitmask), compute the set of computers
    # that get damaged if that subset forms a single group.
    # A virus j damages its computers if S_j is a subset of the group.
    # We need: for a group G (bitmask), damaged(G) = union of S_j for all j where S_j is subset of G.
    
    # Precompute: for each subset S, the damage (union of all virus masks that are subsets of S)
    # We can use SOS (sum over subsets) style DP but we need "union of virus masks for all submasks"
    
    # First, for each mask, store the OR of all virus S_j that equal that mask
    # Then do a "superset sum" to get for each group G, the OR of all virus masks that are subsets of G.
    
    # virus_at[mask] = OR of all S_j where S_j == mask
    # Actually we want: damage[G] = OR of S_j for all j where S_j is subset of G
    # This is the "subset sum" in the OR semiring over supersets.
    
    # Standard approach: damage[G] = OR over all T subset of G of virus_at[T]
    # We can compute this with SOS DP.
    
    full = (1 << N) - 1
    
    # virus_or[mask] = OR of all S_j that exactly equal mask
    virus_or = [0] * (1 << N)
    for mask in viruses:
        virus_or[mask] |= mask
    
    # SOS DP: damage[G] = OR of virus_or[T] for all T subset of G
    # Standard subset sum DP (over OR):
    damage = virus_or[:]
    for i in range(N):
        for g in range(1 << N):
            if g & (1 << i):
                damage[g] |= damage[g ^ (1 << i)]
    
    # Now damage[G] = bitmask of computers damaged if G is a single group
    # But we only care about damage within G, so effective damage = damage[G] & G
    # Actually, S_j subset of G means all bits of S_j are in G, so damage[G] is already subset of G.
    # (since virus_or[mask] = mask for non-empty, and OR of subsets of G is subset of G)
    
    # popcount
    pc = [0] * (1 << N)
    for i in range(1, 1 << N):
        pc[i] = pc[i >> 1] + (i & 1)
    
    # cost[G] = number of damaged computers if G forms one group = popcount(damage[G])
    cost = [0] * (1 << N)
    for g in range(1 << N):
        cost[g] = pc[damage[g]]
    
    # Now we need to partition {0,...,N-1} into groups to minimize total damage.
    # This is a set partition problem. We use DP over subsets.
    # dp[mask] = minimum total damage for partitioning the set 'mask' into groups
    
    # dp[0] = 0
    # dp[mask] = min over all non-empty subsets G of mask: cost[G] + dp[mask ^ G]
    
    # Enumerating all subsets of all masks: O(3^N) which for N=15 is ~14M, feasible.
    
    INF = float('inf')
    dp = [INF] * (1 << N)
    dp[0] = 0
    
    for mask in range(1, 1 << N):
        # Enumerate all non-empty subsets of mask
        sub = mask
        while sub:
            val = cost[sub] + dp[mask ^ sub]
            if val < dp[mask]:
                dp[mask] = val
            sub = (sub - 1) & mask
        # sub=0 is not a valid group (must be non-empty), so we stop
    
    print(dp[full])

solve()

---

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