概要

各警備会社を「選ぶ/選ばない」で全探索すると \(2^N\) 通りになって大きすぎます。
そこで「今までに警備できる施設の集合」をビットマスクで表し、会社を1社ずつ見ながら最小費用を更新する bit DP（部分集合DP） で解きます。

考察

重要な点は、制約が \(N \le 50, M \le 18\) であることです。
\(N\) はそこそこ大きいですが、\(M\) は小さいです。

• 会社の選び方をそのまま全列挙すると \(2^N\)（最大 \(2^{50}\)）で不可能。
• 一方、施設の状態数は \(2^M\)（最大 \(2^{18}=262144\)）で、こちらは現実的。

つまり、「どの会社を選んだか」ではなく
「どの施設までカバーできているか」 を状態に持つのが有効です。

---

各会社 \(i\) がカバーできる施設集合をビットマスク mask[i] に変換します。
例えば \(M=5\) で施設 1,3 を警備できるなら 00101 のように表せます（ビット位置の対応は実装依存）。

DPの意味を次で定義します：

• dp[s] = 「施設集合 s をカバーするための最小費用」

初期状態は何もカバーしていないので dp[0]=0。
会社を1社見るごとに、

• 選ばない：状態そのまま
• 選ぶ：ns = s | mask[i] に遷移し、費用を + C[i]

を行えばよいです。
これは 0/1 ナップサック型の更新なので、コードでは ndp = dp[:] を使って「選ばない場合」を保持してから「選ぶ場合」を反映しています。

最後に、全施設をカバーする状態は ((1<<M)-1) なので、その最小値が答えです。到達不能なら -1 を出力します。

アルゴリズム

1. 入力を受け取り、各会社 \(i\) の警備可能施設列 \(E_{i,*}\) をビットマスク masks[i] に変換する。
2. size = 1<<M、dp を長さ size で用意し、dp[0]=0、他は INF。
3. 会社 \(i=0..N-1\) について以下を実行：
   • ndp = dp[:]
   • すべての状態 s について、dp[s] が有効なら
     • ns = s | masks[i]
     • ndp[ns] = min(ndp[ns], dp[s] + C[i])
   • dp = ndp
4. full = (1<<M)-1 として dp[full] を確認し、INF なら -1、そうでなければその値を出力。

計算量

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

（N=50, M=18 なら約 \(50 \times 262144\) 程度で十分実行可能）

実装のポイント

• 施設集合はビット演算（|, <<）で高速に扱う。

• INF は十分大きく（例: 10**30）してオーバーフローや比較ミスを防ぐ。

• 各会社を1回しか使えないため、更新時は ndp を使って「同じ会社の重複使用」を防ぐ。
  

• 最終状態 full = (1<<M)-1 が作れない場合は -1 を忘れず出力する。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    N, M = map(int, input().split())
    C = list(map(int, input().split()))

    masks = []
    for _ in range(N):
        e = list(map(int, input().split()))
        mask = 0
        for j, v in enumerate(e):
            if v == 1:
                mask |= (1 << j)
        masks.append(mask)

    INF = 10**30
    size = 1 << M
    dp = [INF] * size
    dp[0] = 0

    for i in range(N):
        ndp = dp[:]  # 選ばない場合を保持
        cm = masks[i]
        cost = C[i]
        for s in range(size):
            if dp[s] == INF:
                continue
            ns = s | cm
            v = dp[s] + cost
            if v < ndp[ns]:
                ndp[ns] = v
        dp = ndp

    ans = dp[size - 1]
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。