概要

この問題は、与えられた \(N\) 個の警備会社の中から、全 \(M\) 箇所の施設を少なくとも1つの会社が警備している状態にするための最小費用を求める問題です。これは「集合被覆問題」と呼ばれる有名な問題の一種ですが、施設の数 \(M\) が小さいため、動的計画法（DP）を用いて効率的に解くことができます。

考察

1. 全探索の検討

まず、警備会社の選び方を全探索することを考えます。各会社を「選ぶ」か「選ばない」かの2通りがあるため、組み合わせの総数は \(2^N\) 通りとなります。本問題では \(N \leq 50\) であるため、\(2^{50} \approx 1.12 \times 10^{15}\) となり、制限時間内に計算を終えることは不可能です。

2. 状態の圧縮（ビット表現）

一方で、施設の数 \(M\) に注目すると \(M \leq 18\) と非常に小さいことがわかります。どの施設が警備されているかという「状態」は、\(2^M = 2^{18} = 262,144\) 通りしかありません。 このように、集合の状態を整数（ビットマスク）で表現する手法が有効です。具体的には、施設 \(j\) が警備されているなら \(j\) 番目のビットを \(1\)、そうでなければ \(0\) とすることで、全施設の警備状況を \(0\) から \(2^M-1\) までの整数で表せます。

3. 動的計画法の適用

「現在の警備状況」を状態として持ち、新しい警備会社を追加したときにどのように状態が遷移するかを考えることで、以下のDPを構築できます。 - dp[mask] : 施設集合 mask を警備するために必要な最小コスト

新しい警備会社（警備範囲を c_mask、コストを cost とする）を契約する場合、現在の状態 mask は mask | c_mask（ビット和）へと遷移します。

アルゴリズム

ビットDP（Bitmask DP）

1. 初期化:
   • 長さ \(2^M\) の配列 dp を用意し、非常に大きな値（無限大）で初期化します。
   • dp[0] = 0 とします（どの施設も警備していない状態のコストは \(0\)）。
2. 遷移:
   • 各警備会社 \(i = 1, \dots, N\) について、以下の処理を行います。
   • すべての現在の状態 mask（\(0\) から \(2^M-1\) まで）を走査します。
   • dp[mask] が無限大でない場合、新しい状態 new_mask = mask | company_mask[i] を計算します。
   • dp[new_mask] を min(dp[new_mask], dp[mask] + cost[i]) で更新します。
3. 結果:
   • すべての施設が警備された状態は、すべてのビットが \(1\) である (1 << M) - 1 です。
   • dp[(1 << M) - 1] が初期値のままなら -1 を、そうでなければその値を出力します。

計算量

• 時間計算量: \(O(N \cdot 2^M)\)
  • 警備会社の数 \(N\) と、状態数 \(2^M\) の積になります。
  • \(50 \times 2^{18} \approx 1.3 \times 10^7\) となり、制限時間内に十分収まります。
• 空間計算量: \(O(2^M)\)
  • DPテーブルのサイズが \(2^M\) となります。

実装のポイント

• ビット演算: 施設 \(j\) を警備できることを 1 << j で表現し、会社全体の警備範囲を OR 演算 (|) でまとめておくと、遷移の計算が高速になります。

• 入出力の高速化: \(N, M\) の値に対して入力データ（\(E_{i,j}\)）が多いため、Pythonでは sys.stdin.read().split() などを使って一括で読み込むと実行時間を短縮できます。

• 遷移の順序: 各警備会社についてループを回す際、同じ会社を複数回選ばないように注意が必要です。本実装のように、各会社ごとにテーブル全体を更新する形にすれば、自然に「各会社を1回使うか使わないか」の選択を表現できます。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする（高速化のため）
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 警備会社の数, M: 施設の数
    N = int(data[0])
    M = int(data[1])
    
    # C: 各警備会社の契約費用
    # 2番目のインデックスからN個が費用データ
    costs = [int(x) for x in data[2:N+2]]
    
    # 各警備会社が警備できる施設をビットマスクとして表現する
    # 施設jを警備できる場合、マスクのj番目のビットを1にする
    company_masks = []
    # E_{i,j} のデータはインデックス N+2 から始まる
    idx = N + 2
    for i in range(N):
        mask = 0
        for j in range(M):
            if data[idx] == '1':
                mask |= (1 << j)
            idx += 1
        # どの施設も警備できない会社は選ぶ必要がないため除外（費用は1以上のため）
        if mask > 0:
            company_masks.append((costs[i], mask))
    
    # DPテーブルの初期化
    # dp[mask] は、ビットマスクで表される施設集合を警備するための最小コスト
    # 2^M 通りの状態がある (M <= 18 なので最大 262,144)
    num_masks = 1 << M
    inf = 10**18  # 十分に大きな値
    dp = [inf] * num_masks
    dp[0] = 0  # 最初はどの施設も警備していない状態（コスト0）
    
    # 各警備会社について、DPテーブルを更新していく
    for cost, c_mask in company_masks:
        # 現在のDPテーブルの状態を走査
        for mask in range(num_masks):
            # まだ到達不可能な状態（inf）はスキップ
            if dp[mask] == inf:
                continue
            
            # 新しい状態：現在の施設集合に、この会社の警備範囲を追加（ビットOR演算）
            new_mask = mask | c_mask
            new_cost = dp[mask] + cost
            
            # 新しい状態のコストが現在の記録より安ければ更新
            if dp[new_mask] > new_cost:
                dp[new_mask] = new_cost
                
    # 全ての施設が警備された状態（全てのビットが1のマスク）の最小コストを取得
    ans = dp[num_masks - 1]
    
    # 初期値のまま（inf）であれば、全ての施設を警備する方法が存在しない
    if ans == inf:
        print("-1")
    else:
        print(ans)

if __name__ == '__main__':
    solve()

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