概要

\(N\) 社の警備会社から何社かを選び、\(M\) 箇所すべての施設を警備できるようにする最小コストを求める問題です。これは典型的な重み付き集合被覆問題（Weighted Set Cover）であり、\(M \leq 18\) という制約を活かしてビットマスクDPで解きます。

考察

素朴なアプローチ

\(N\) 社からいくつかを選ぶ組み合わせは \(2^N - 1\) 通りあります。\(N \leq 50\) なので \(2^{50} \approx 10^{15}\) 通りとなり、全列挙は到底間に合いません。

重要な気づき：施設数が小さい

\(M \leq 18\) に注目します。「どの施設が警備済みか」という状態は、各施設を1ビットで表すと \(2^M \leq 2^{18} = 262144\) 通りしかありません。

例えば \(M = 3\) のとき、施設の警備状況は以下のようにビットマスクで表せます： - 000（= 0）：どの施設も未警備 - 101（= 5）：施設1と施設3が警備済み - 111（= 7）：すべて警備済み（ゴール）

解法の方針

各警備会社 \(i\) が警備できる施設の集合もビットマスク \(\text{cover}[i]\) で表します。警備会社 \(i\) を選ぶと、現在の警備状況 \(\text{mask}\) が \(\text{mask} \mid \text{cover}[i]\) に更新されます。

これは 0-1ナップサック問題 と同様の構造を持ちます。各会社を「使う or 使わない」と選びながら、最小コストで全施設をカバーする状態に到達すればよいのです。

アルゴリズム

ビットマスクDP を用います。

1. 状態の定義: \(dp[\text{mask}]\) = 施設集合 \(\text{mask}\) をちょうど警備済みにするために必要な最小コスト
2. 初期値: \(dp[0] = 0\)（何も警備しない状態はコスト0）、それ以外は \(\infty\)
3. 遷移: 警備会社 \(i = 1, 2, \ldots, N\) を順に処理し、各状態 \(\text{mask}\) に対して： $\(dp[\text{mask} \mid \text{cover}[i]] = \min(dp[\text{mask} \mid \text{cover}[i]],\; dp[\text{mask}] + C_i)\)$
4. 答え: \(dp[(1 \ll M) - 1]\)（全施設が警備済みの状態）。\(\infty\) のままなら \(-1\) を出力。

各会社を1回ずつしか選べないようにするため、0-1ナップサックと同様に mask を降順に走査 します。これにより、同じ会社を重複して適用することを防ぎます。

具体例

\(N=3, M=3\)、コスト \(C = [5, 3, 4]\)、各社の警備範囲が 110, 011, 100 の場合： - 会社1: \(\text{cover}[1] = 011_2 = 3\)（施設1,2を警備） - 会社2: \(\text{cover}[2] = 110_2 = 6\)（施設2,3を警備） - 会社1と会社2を選ぶと \(3 \mid 6 = 7 = 111_2\)（全施設カバー）、コスト \(5 + 3 = 8\)

計算量

• 時間計算量: \(O(N \cdot 2^M)\)
  • \(N \leq 50\), \(2^M \leq 2^{18} = 262144\) なので、約 \(1.3 \times 10^7\) 回の処理で十分高速
• 空間計算量: \(O(2^M)\)
  • DPテーブルのサイズ

実装のポイント

• 各警備会社の警備可能施設をビットマスクに変換する際、\(j\) 番目の施設が警備可能なら mask |= (1 << j) とする

• 同じ会社を2回以上使わないために、0-1ナップサック同様 mask を降順（大きい方から小さい方）にループ する。昇順にすると、同じ会社の効果が複数回適用される恐れがある

• コストが最大 \(10^9\) で \(N\) 社選ぶと最大 \(5 \times 10^{10}\) になるため、float('inf') や64ビット整数で扱えば問題ない

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    C = []
    for i in range(N):
        C.append(int(input_data[idx])); idx += 1
    
    cover = []
    for i in range(N):
        mask = 0
        for j in range(M):
            e = int(input_data[idx]); idx += 1
            if e == 1:
                mask |= (1 << j)
        cover.append(mask)
    
    full = (1 << M) - 1
    INF = float('inf')
    
    # dp[mask] = minimum cost to cover the set of facilities represented by mask
    dp = [INF] * (full + 1)
    dp[0] = 0
    
    for i in range(N):
        # Iterate in reverse to avoid using same company twice? 
        # No, since each company is considered once and we can either take it or not,
        # but we need to iterate properly. Actually, since we just OR masks,
        # we can iterate forward through companies and for each, update all masks.
        # But we need to be careful: standard set cover DP.
        # We process each company and for each existing state, try adding it.
        for mask in range(full, -1, -1):
            if dp[mask] < INF:
                new_mask = mask | cover[i]
                if dp[new_mask] > dp[mask] + C[i]:
                    dp[new_mask] = dp[mask] + C[i]
    
    if dp[full] == INF:
        print(-1)
    else:
        print(dp[full])

main()

---

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