公式
E - グループ分けとウイルス感染 / Group Division and Virus Infection 解説 by admin
deepseekv3.1概要
\(N\) 台のコンピュータをいくつかのグループに分割し、\(M\) 種類のウイルスによる被害を受けるコンピュータの台数を最小化する問題です。各ウイルスは特定のコンピュータ集合に感染し、その集合が単一グループに含まれる場合のみ感染が成功します。
考察
素朴にすべてのグループ分けを列挙しようとすると、ベル数 \(B(N)\) が \(N=15\) で約 \(10^9\) 通りとなり現実的ではありません。代わりに、以下の観察が鍵となります：
- ウイルス \(j\) が感染するためには、その対象集合 \(S_j\) が単一グループに含まれる必要があります
- グループ分けを固定した時、被害を受けるコンピュータは、各グループ \(G\) に対して \(S_j \subseteq G\) となる \(S_j\) の和集合です
- この問題は、全体集合 \(\{1,2,\dots,N\}\) の部分集合 \(sub\) ごとに「\(sub\) を1つのグループとした時に感染するコンピュータの集合」を事前計算し、部分集合和DPで解くことができます
アルゴリズム
- 前処理: 各ウイルスの対象集合をビットマスクで表現します
- SOS DP: すべての部分集合 \(sub\) について、\(sub\) に含まれるウイルス対象集合の和集合を計算します
- \(infected[sub]\): \(S_j \subseteq sub\) となるすべての \(S_j\) の和集合
- これはSum Over Subsets (SOS) DPのORバージョンで効率的に計算できます
- DP計算: 部分集合和DPで最適解を求めます
- \(dp[mask]\): \(mask\) で表されるコンピュータ集合に対する最小被害数
- \(dp[mask] = \min_{sub \subseteq mask} \{dp[mask - sub] + |infected[sub]|\}\)
- すべての空でない部分集合 \(sub\) について遷移を試します
計算量
- 時間計算量: \(O(3^N + M + N \cdot 2^N)\)
- SOS DP: \(O(N \cdot 2^N)\)
- DP部分: \(O(3^N)\) (すべての部分集合の反復)
- 空間計算量: \(O(2^N)\)
実装のポイント
ビット演算を活用した効率的な部分集合の列挙
SOS DPによる高速な前計算
ウイルス対象集合が空の場合の処理（コードでは自然に処理されます）
\(N=15\) なので \(2^{15} = 32768\) 状態のDPが可能
ソースコード
def main():
import sys
data = sys.stdin.read().split()
if not data:
print(0)
return
it = iter(data)
N = int(next(it)); M = int(next(it))
viruses = []
for _ in range(M):
k = int(next(it))
lst = []
for _ in range(k):
lst.append(int(next(it)))
viruses.append(lst)
# 各ウイルスjについて、S_jの集合をビットマスクで表現
virus_masks = []
for lst in viruses:
mask = 0
for x in lst:
mask |= (1 << (x-1))
virus_masks.append(mask)
# 全コンピュータの集合
all_computers = (1 << N) - 1
# dp[partition]: グループ分けpartitionの下で被害を受けるコンピュータの集合
# partitionは、グループ分けをビットマスクの集合で表現する代わりに、
# 各コンピュータが属するグループの代表（最小番号）でラベル付けする方法を用いる
# ここでは、グループ分けを有効に列挙するために、subset-basedのDPを行う
# グループ分けの表現: 各コンピュータiについて、そのグループの最小番号のコンピュータを代表とする
# 例えば、3台のコンピュータ[0,1,2]について:
# グループ分け {{0},{1,2}} は、代表が[0,1,1]となる（0のグループの代表は0、1と2のグループの代表は1）
# しかし、Nが15までなので、グループ分けの数はベル数B(15)≈10^9程度となり全列挙は不可能
# 別のアプローチ: 被害を受けるコンピュータの集合を最小化したい
# 各ウイルスjは、S_jが1つのグループに含まれる場合にのみS_j全体が被害を受ける
# したがって、グループ分けをPとするとき、被害を受けるコンピュータの集合は:
# U_{j: S_jがPで1つのグループに含まれる} S_j
# これを最小化する
# 逆に、被害を受けないようにするには、各ウイルスjについてS_jを2つ以上のグループに分割すれば良い
# つまり、あるグループ分けPの下で、ウイルスjが被害を与えるか否かは、S_jがPのあるグループに包含されるかどうか
# 重要な観察: グループ分けPを固定したとき、ウイルスjが被害を与えるためには、S_jがPのいずれかのグループの部分集合である必要がある
# つまり、あるグループG in Pがあって、S_j ⊆ G
# したがって、被害を受けるコンピュータの集合は、あるグループG in Pに対してS_j ⊆ GとなるようなjについてのS_jの和集合
# ここで、グループ分けPは、コンピュータ集合の分割である
# 最小化問題を、包含関係で考える:
# F(P) = ∪ { S_j : ∃G in P such that S_j ⊆ G }
# 目標: min_P |F(P)|
# 別の視点: 各コンピュータiが被害を受けるか否かは、それを含むようなS_jで、かつS_jが単一グループに含まれるようなjが存在するか
# また、グループ分けPは、ある同値関係（同じグループに属する）を定める
# この問題は、Nが小さい（最大15）ので、ビットDPが使える
# 考えうる方針:
# precompute: 各ウイルスjのS_j（ビットマスク）
# for each subset T of computers (which will be the set of infected computers):
# あるグループ分けPが存在して、F(P) = T となるか？
# そして、|T|を最小化する
# しかし、Tが被害の集合であるための必要条件は？
# もし、あるウイルスjのS_jがTに含まれないなら、そのウイルスjはブロックされなければならない
# つまり、S_jは2つ以上のグループに跨がっている必要がある
# 逆に、Tが被害の集合であるためには、以下の条件が必要:
# (1) 各ウイルスjについて、S_j ⊆ T ならば、S_jは単一グループに含まれる（これはグループ分け次第）
# (2) S_j ⊈ T ならば、S_jは2つ以上のグループに跨がっている（ブロックされる）
# 実は、Tが被害の集合であるための必要十分条件は、Tが以下の条件を満たすこと:
# "あるグループ分けPが存在して、T = ∪ { S_j : S_jがPの某グループの部分集合 }"
# そして、そのグループ分けPは、Tを部分集合として含むようなグループに分解できる
# さらに、Tがindependentな集合（？）ではない
# 別のアプローチ: グループ分けPを直接扱うのはベル数が大きいので無理
# しかし、N=15なので、全部分集合（2^15=32768）は扱える
# 実際、各グループはコンピュータの部分集合である
# そして、グループ分けPは、全体集合の分割である
# 被害の集合Tは、Pのグループのいくつかの和集合として表現できるS_jの和集合である
# ここで、以下のようなDPを考える:
# dp[mask] = グループ分けがmaskで表されるコンピュータの集合について、その内部で被害を受けるコンピュータの集合の最小サイズ？
# ただし、maskはビットマスク
# しかし、グループ分け全体を考慮する必要がある
# 実は、この問題は、以下のようにして解ける:
# 最適なグループ分けでは、各グループは"connected"である必要はない
# 被害を最小化するには、大きなグループを作るとウイルスが通過しやすく、小さなグループを作るとブロックしやすい
# 公式解法のアイデア:
# 各ウイルスjは、S_jが単一グループに含まれるときに通過する
# 通過するウイルスjの集合をXとするとき、被害を受けるコンピュータの集合は ∪_{j in X} S_j
# グループ分けPが与えられたとき、X = { j : ∃G in P, S_j ⊆ G }
# 逆に、Xを通過させるウイルスの集合とするとき、Xに属するウイルスjのS_jは全て単一グループに含まれなければならない
# つまり、グループ分けPは、各j in XについてS_jを包含するようなグループを持たなければならない
# また、Xに属さないウイルスjは、S_jが2つ以上のグループに跨がるようにしなければならない
# 通過させるウイルスの集合Xを固定したとき、それが実現可能であるためには、Xに属するウイルスのS_jたちが"互いに矛盾しない"必要がある
# つまり、ある2つのS_jとS_kが交わるならば、それらは同じグループに含まれねばならないので、S_j ∪ S_kも同じグループに含まれる必要がある
# これを繰り返すと、Xに属するウイルスにより接続されたコンピュータの集合は、1つのグループに含めなければならない
# したがって、Xが与えられたとき、それが実現可能であるためには、Xに属するウイルスのS_jで接続されるグラフの連結成分ごとに、グループが作れなければならない
# そして、そのようなグループ分けが存在するとき、被害を受けるコンピュータの集合は ∪_{j in X} S_j
# したがって、問題は、以下の条件を満たすようなXの選び方の中で、|∪_{j in X} S_j|を最小化する問題に帰着する:
# 各連結成分（S_jたちで生成されるグラフ）が、グループ分けの1グループを形成できる（つまり、特に条件はない）
# 実は、Xの選び方について、上記の条件は常に満たされる?なぜなら、連結成分をそのグループとすれば良いから
# つまり、任意のXについて、それに対応するグループ分けが存在する?
# ただし、Xに属するウイルスのS_j们が覆盖するコンピュータ集合を、連結成分ごとにグループとすれば良い
# そして、Xに属さないウイルスについては、そのS_jが複数のグループに跨がっているかチェックする必要がある
# しかし、Xの選び方により、連結成分をグループとすれば、Xに属さないウイルスjのS_jが単一グループに含まれることはない?
# 必ずしもそうではない: 例えば、Xに属さないウイルスjのS_jが、たまたまある連結成分に完全に含まれる可能性がある
# すると、そのウイルスjも通過してしまうので、Xで選んだつもりでも実際にはX∪{j}が通過してしまう
# therefore、Xを選んだとき、実際に通過するウイルスはXだけであるためには、Xは以下の条件を満たさなければならない:
# For every virus j not in X, S_j is not contained in any connected component of the graph induced by X.
# induced graph: コンピュータを頂点とし、Xに属するウイルスjのS_jが辺（完全クリーク）を生成する? rather, S_j itself is a complete subgraph?
# actually, the connected components are defined by the graph where we connect two computers if they appear together in some S_j in X.
# So, for X to be valid, for every j not in X, S_j is not a subset of any connected component of the graph (V, E) with E = { (u,v) : there exists j in X such that u,v in S_j }.
# Note: since each S_j is a set, the graph is actually a union of cliques (each S_j forms a clique).
# Thus, the problem becomes: find a set X of viruses such that:
# For every j not in X, S_j is not contained in any connected component of the graph induced by X.
# and minimize |∪_{j in X} S_j|.
# And note that the connected components of the graph induced by X are exactly the groups in the partition we would use.
# So, we can iterate over all subsets X of viruses (2^M) but M can be up to 500, which is too large.
# Instead, we can iterate over the connected components of the graph on computers? Or use state that represents the connected components of the graph on computers.
# Since N is only 15, we can use bitmask DP over the computers.
# Let's define:
# dp[mask] = the set of viruses X that have been considered for the component mask, but actually we want the minimum number of infected computers.
# Actually, we can define:
# dp[mask] = minimum number of infected computers achievable for the set of computers in mask, by choosing some set X of viruses that satisfy the condition within mask.
# But note: the condition must hold for all viruses j: if j is not in X, then S_j is not contained in any connected component of the graph induced by X.
# However, within mask, we only care about viruses that have S_j subset of mask.
# Another idea: we can use the following recurrence for the grouping:
# dp[mask] = min_{nonempty subset sub of mask} [ dp[mask - sub] + cost(sub) ]
# where cost(sub) is the set of computers that must be infected if we make sub a group.
# But what is cost(sub)? In the group sub, which viruses will pass? Those viruses j such that S_j is subset of sub.
# So, cost(sub) = union of S_j over all j such that S_j ⊆ sub.
# However, is this recurrence valid?
# Consider a group sub. If we make sub a group, then all viruses j with S_j ⊆ sub will pass, and their S_j will be infected.
# Also, for the recurrence to work, we need that no virus j with S_j not contained in sub will pass? But actually, if S_j is not contained in sub, it might be split between sub and other groups, so it will be blocked.
# Therefore, the recurrence is:
# dp[mask] = min_{sub ⊆ mask, sub != empty} [ dp[mask - sub] + |∪_{j: S_j ⊆ sub} S_j| ]
# BUT: note that the same computer might be infected in multiple groups? However, in the union we take the set of infected computers, so duplicate is not counted.
# However, is this correct? Let's test with a small case.
# Example: N=2, computers {0,1}.
# Virus1: {0}
# Virus2: {1}
# Virus3: {0,1}
# If we put both in one group (sub={0,1}), then cost(sub) = union of S_j for j with S_j ⊆ sub:
# all three viruses have S_j ⊆ sub, so cost(sub) = {0,1} -> size2.
# If we put them in two groups: sub1={0}, sub2={1}.
# For sub1: viruses with S_j ⊆ {0} are Virus1 -> cost={0}
# For sub2: viruses with S_j ⊆ {1} are Virus2 -> cost={1}
# total cost = |{0} ∪ {1}| =2.
# But actually, in the two-group case, Virus3 is blocked because it spans two groups. So the infected computers are only {0,1}? wait, but Virus1 and Virus2 are not blocked because they are in single groups. So indeed infected are {0,1}.
# However, can we do better? In this case, no.
# Now, consider if we have only Virus3. Then:
# One group: cost={0,1}
# Two groups: cost=0 because for each group, no virus has S_j contained in the group (Virus3's S_j is not contained in either group).
# So dp[3] = min( dp[0]+2, dp[1]+0, dp[2]+0 ) = min(2,0,0)=0.
# This is correct.
# Therefore, the recurrence seems correct.
# So, we have:
# dp[0] = 0
# for mask from 1 to (1<<N)-1:
# dp[mask] = min_{sub ⊆ mask, sub != empty} [ dp[mask - sub] + cost(sub) ]
# where cost(sub) = the union of all S_j that are subsets of sub.
# However, note: the same computer might be counted in multiple groups? But in the recurrence, we are taking the union of infected computers from different groups, and we add the cost for each group. But actually, the groups are disjoint, so the union is disjoint.
# Therefore, the recurrence is correct.
# How to compute cost(sub) for every subset sub?
# Precompute an array infected[sub] for each subset sub.
# infected[sub] = the union of all S_j that are subsets of sub.
# How to compute infected[sub]?
# Initialize infected[sub] = 0.
# For each virus j with mask S_j_mask:
# For each sub that contains S_j_mask:
# infected[sub] |= S_j_mask
# This would take O(M * 2^N) which is 500 * 32768 ~ 16e6, which is acceptable.
# However, we can do faster using SOS DP (Sum Over Subsets) style.
# For each virus j, let A[ S_j_mask ] |= S_j_mask [ but actually, we want to OR all S_j_mask that are subsets of sub]
# Then, we can do:
# infected[sub] = 0
# for each virus j:
# if (S_j_mask & sub) == S_j_mask: // i.e., S_j_mask is subset of sub
# infected[sub] |= S_j_mask
# But to avoid iterating over all viruses for each sub, we can use:
# Let F[sub] = 0
# For each virus j, let F[ S_j_mask ] |= S_j_mask
# Then, infected[sub] = OR_{subseteq of sub} F[sub]? Actually, we want to OR all F[s] for ssubseteq of sub.
# This is exactly the SOS DP for OR.
# Steps:
# Initialize F[sub] = 0 for all sub.
# For each virus j:
# F[ S_j_mask ] |= S_j_mask
# Then, for i in range(N):
# for sub in range(1<<N):
# if sub has the i-th bit:
# F[sub] |= F[sub without i-th bit]
# But wait: we want infected[sub] = OR_{s ⊆ sub} F[s] = OR_{s ⊆ sub} [ if there is a virus with S_j_mask = s, then s else 0 ]
# However, this is exactly the SOS DP for the OR operation.
# However, note: F[s] might have more than one virus? But ORing the masks is the same as taking the union.
# So, we can compute infected[sub] by:
# infected = [0] * (1<<N)
# for j in range(M):
# s = virus_masks[j]
# infected[s] |= s # but actually, if there are multiple viruses with the same s, this is the same.
# Then, do SOS:
# for i in range(N):
# for sub in range(1<<N):
# if sub & (1<<i):
# infected[sub] |= infected[sub ^ (1<<i)]
# However, this will work because if s is a subset of sub, then s will be considered in the SOS.
# Therefore, the algorithm:
# Precompute infected[0..2^N-1] using SOS DP.
# Initialize dp[0] = 0
# For mask from 1 to (1<<N)-1:
# dp[mask] = inf
# sub = mask
# while sub: # iterate over non-empty subsets of mask
# candidate = dp[mask - sub] + bin(infected[sub]).count('1')
# if candidate < dp[mask]:
# dp[mask] = candidate
# sub = (sub-1) & mask
# Then output dp[(1<<N)-1]
# However, note: the cost for a group sub is |infected[sub]|, which is the number of computers that would be infected in that group.
# But is this correct? infected[sub] is the union of all S_j that are contained in sub. This is exactly the set of computers that would be infected in the group sub.
# Let's test with the example above:
# For sub={0}: infected[{0}] = {0} (because Virus1 is contained) -> size1.
# For sub={1}: infected[{1}] = {1} -> size1.
# For sub={0,1}: infected[{0,1}] = {0,1} (because all three viruses are contained) -> size2.
# Then dp[3] = min( dp[2] + cost({0}) , dp[1] + cost({1}), dp[0] + cost({0,1}) )
# = min( dp[2] + 1, dp[1] + 1, 0+2 )
# Now, dp[1] = cost({0}) = 1? but wait, mask=1 is the set {0}. Then dp[1] = min over nonempty subsets of {0}: only sub={0} -> dp[0] + cost({0}) = 0+1=1.
# Similarly, dp[2] =1.
# So dp[3] = min(1+1, 1+1, 2) = min(2,2,2)=2.
# But we also have the option to take sub={0} and then sub={1} in the recurrence for mask=3? Actually, the recurrence considers one group at a time. So when we take sub={0}, we get dp[3] = dp[3-1] + cost({0}) = dp[2] + 1 = 1+1=2.
# Then we take sub={1}, we get dp[3] = dp[1] + cost({1}) = 1+1=2.
# Then we take sub={0,1}, we get 0+2=2.
# So it works.
# However, the example with only Virus3 (S_j={0,1}):
# infected[{0}] = 0 (because no virus has S_j contained in {0}) -> cost0.
# infected[{1}] =0 -> cost0.
# infected[{0,1}] = {0,1} -> cost2.
# Then dp[3] = min( dp[2] +0, dp[1]+0, 0+2 ) = min(0,0,2) =0.
# How to compute dp[1]? mask=1: subsets are {0}. cost0. so dp[1]=0.
# Similarly dp[2]=0.
# So correct.
# Therefore, we will implement this.
# Precompute infected for all subsets using SOS DP.
infected = [0] * (1 << N)
for s_mask in virus_masks:
# For each virus mask, mark that the set s_mask is to be ORed.
infected[s_mask] |= s_mask
# SOS DP: for each subset, OR all infected[s] for s ⊆ sub
for i in range(N):
for sub in range(1 << N):
if sub & (1 << i):
infected[sub] |= infected[sub ^ (1 << i)]
# Now, compute the number of infected computers for each subset: actually, infected[sub] is already the set.
# Instead, we can precompute popcount for each infected[sub]
cost_arr = [bin(infected[i]).count('1') for i in range(1<<N)]
# Initialize dp
dp = [10**9] * (1 << N)
dp[0] = 0
for mask in range(1, 1 << N):
sub = mask
while sub:
candidate = dp[mask - sub] + cost_arr[sub]
if candidate < dp[mask]:
dp[mask] = candidate
sub = (sub - 1) & mask
print(dp[(1<<N)-1])
if __name__ == '__main__':
main()
この解説は deepseekv3.1 によって生成されました。
投稿日時:
最終更新: