公式

E - グループ分けとウイルス感染 / Group Division and Virus Infection 解説 by admin

gemini-3.5-flash-thinking

概要

この問題は、15台という少ないコンピュータ（\(N \leq 15\)）をいくつかのグループに分割し、ウイルスによる被害を受けるコンピュータの総数を最小化する問題です。 各グループ内で完結するウイルスの被害をあらかじめ計算しておき、ビットDP（集合DP）を用いて最適なグループ分け（集合の分割）を探索することで解くことができます。

考察

1. グループ内の被害の独立性

コンピュータの集合をいくつかのグループ \(T_1, T_2, \ldots, T_k\) に分割したとします（これらは互いに素で、和集合が全体集合になります）。 ウイルス \(j\) の感染対象 \(S_j\) が被害をもたらすのは、\(S_j\) がいずれか1つのグループ \(T_i\) に完全に含まれる（\(S_j \subseteq T_i\)）ときのみです。

したがって、グループ \(T\) を1つ作ったときに、そのグループ内で被害を受けるコンピュータの集合は、以下のようになります。 $\(U(T) = \bigcup_{S_j \subseteq T} S_j\)\( このグループ \)T\( における被害台数を \)C[T] = |U(T)|\( と定義すると、全体のグループ分けに対する被害台数の総和は、各グループの被害台数の和 \)\sum C[T_i]$ となります。

2. \(C[T]\) の高速な計算（SOS DP の導入）

すべての \(T\)（\(0 \leq T < 2^N\)）について \(C[T]\) を愚直に計算すると、ウイルスの数 \(M\) が最大 500 であるため、\(O(M \cdot 2^N)\) の計算量がかかります。\(N=15\) では \(2^{15} = 32,768\) なので、これでも間に合いますが、よりスマートかつ高速に求めるために SOS DP (Sum Over Subsets DP / 高速ゼータ変換) を利用します。

各ウイルス \(j\) について、初期値として W[S_j] = S_j としておきます（ビットマスクで表現）。 その後、SOS DP の要領で「部分集合の和集合」を累積していくことで、すべての \(T\) に対して \(S_j \subseteq T\) となるすべての \(S_j\) の論理和（和集合）W[T] を \(O(N 2^N)\) で求めることができます。 \(C[T]\) は W[T] の立っているビット数（popcount）となります。

3. グループ分割の最適化（ビットDP）

コンピュータの集合 \(S\) をグループ分けしたときの最小被害台数を dp[S] とします。 集合 \(S\) から、1つのグループ \(T\)（\(T \subseteq S\) かつ \(T \neq \emptyset\)）を切り出すことを考えると、遷移式は以下のようになります。 $\(\text{dp}[S] = \min_{T \subseteq S, T \neq \emptyset} (C[T] + \text{dp}[S \setminus T])\)$

この遷移を素直に行うと、すべての \(S\) についてその部分集合 \(T\) を走査するため、計算量は \(O(3^N)\) になります。 \(3^{15} \approx 1.43 \times 10^7\) であり、制限時間内に十分実行可能です。

さらに、グループを切り出す順番による重複（例えば、\(\{1, 2\}\) と \(\{3\}\) に分ける遷移と、\(\{3\}\) と \(\{1, 2\}\) に分ける遷移）を排除するため、「\(S\) のうち最も右にある立っているビット（LSB）を必ず含むグループ \(T\) のみを選ぶ」という工夫を施します。これにより、遷移の探索数を約半分に削減できます。

アルゴリズム

ステップ 1: ウイルスの情報をビットマスクに変換

各ウイルス \(j\) の感染対象 \(S_j\) をビット配列（整数値） mask に変換します。

ステップ 2: SOS DP による \(C[T]\) の計算

  1. サイズ \(2^N\) の配列 W を \(0\) で初期化します。
  2. 各ウイルス \(j\) の mask に対し、W[mask] |= mask とします。
  3. 以下のループ（SOS DP）により、各 mask に対し、その部分集合となるウイルスの感染対象の和集合を計算します。 
    
for i in range(N):
   for mask in range(1 << N):
       if (mask >> i) & 1:
           W[mask] |= W[mask ^ (1 << i)]
  4. 各 \(T\) について、C[T] = popcount(W[T]) を計算します。

ステップ 3: ビットDPによる最小値の探索

  1. dp 配列を \(0\) で初期化します。
  2. \(S\) を \(1\) から \(2^N - 1\) まで昇順に走査します。
  3. \(S\) の LSB（最下位ビット）を lsb = S & -S として取得し、残りの集合を rem = S ^ lsb とします。
  4. rem の部分集合 T_prime をビット演算を用いて列挙し、T = T_prime | lsb を1つのグループとして切り出す遷移を行います。 $\(\text{dp}[S] = \min_{T' \subseteq \text{rem}} (C[T' \cup \{\text{lsb}\}] + \text{dp}[\text{rem} \setminus T'])\)$
  5. 最終的な答えは dp[(1 << N) - 1] となります。

計算量

  • 時間計算量: \(O(M + N 2^N + 3^N)\)

    • ウイルスの入力処理と初期化: \(O(M)\)
    • SOS DP による W の計算: \(O(N 2^N)\)
    • ビットDPによる遷移: \(O(3^N)\)
    • \(N = 15, M = 500\) のとき、全体の計算回数は約 \(1.5 \times 10^7\) 回となり、Pythonでも高速に動作します。

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

    • W, C, dp テーブルのサイズはいずれも \(2^N\) です。
    • \(N = 15\) のとき \(2^{15} = 32,768\) 個の整数を保持するだけなので、メモリ使用量は数メガバイト程度と極めて少量です。

実装のポイント

  1. 部分集合の高速な列挙: ある集合 rem の部分集合 T_prime を降順に列挙する際、以下のビット演算テクニックを使用しています。

    T_prime = rem
while T_prime > 0:
   # (T_prime に関する処理)
   T_prime = (T_prime - 1) & rem

    この手法を用いることで、立っているビットのみを対象とした効率的な部分集合の列挙が \(O(3^N)\) で可能になります。

  2. 重複排除による定数倍高速化: lsb を用いて「特定の1要素を必ず含むグループ」のみを切り出すことで、遷移の探索空間を狭め、無駄な重複計算を完全に防いでいます。

    ソースコード

import sys

def main():
    # 入力を一度にすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    idx = 2
    masks = []
    for _ in range(M):
        k = int(input_data[idx])
        idx += 1
        mask = 0
        for _ in range(k):
            v = int(input_data[idx]) - 1
            idx += 1
            mask |= (1 << v)
        masks.append(mask)
        
    # SOS DP (Sum Over Subsets) を用いて、各部分集合 T に対して
    # T に完全に含まれるウイルスの感染対象の和集合のマスク W[T] を計算する
    W = [0] * (1 << N)
    for mask in masks:
        W[mask] |= mask
        
    for i in range(N):
        for mask in range(1 << N):
            if (mask >> i) & 1:
                W[mask] |= W[mask ^ (1 << i)]
                
    # popcount テーブルの作成
    popcount = [0] * (1 << N)
    for i in range(1 << N):
        popcount[i] = popcount[i >> 1] + (i & 1)
        
    # 各部分集合 T が1つのグループを形成したときの、そのグループ内での被害台数 C[T]
    C = [popcount[W[i]] for i in range(1 << N)]
    
    # DP[S]: コンピュータの集合 S をいくつかのグループに分けたときの最小被害台数
    dp = [0] * (1 << N)
    for S in range(1, 1 << N):
        # S のうち最も右にある立っているビット (LSB) を取り出す
        # LSB を含むグループ T を選ぶことで、重複を排除し遷移数を約半分にする
        lsb = S & -S
        rem = S ^ lsb
        val = C[lsb] + dp[rem]
        
        # rem の部分集合 T_prime を列挙する
        T_prime = rem
        while T_prime > 0:
            v = C[T_prime | lsb] + dp[rem ^ T_prime]
            if v < val:
                val = v
            T_prime = (T_prime - 1) & rem
        dp[S] = val
        
    print(dp[(1 << N) - 1])

if __name__ == '__main__':
    main()

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

投稿日時:
最終更新: