概要

この問題は、「各警備会社が担当できる施設の集合」と「契約費用」が与えられたとき、すべての施設を少なくとも1回はカバーするように会社を選び、合計費用を最小化する問題です。
施設数 \(M\) が \(18\) 以下と小さいので、施設の被覆状況をビットマスクで表して動的計画法を行うのが有効です。

考察

まず素朴に考えると、\(N\) 社の中から選ぶ・選ばないを全探索すれば答えは求まります。
しかし、その方法は \(2^N\) 通りを調べることになり、\(N \leq 50\) では現実的ではありません。

一方で、この問題では施設数 \(M\) が小さいことが重要です。
「どの会社を選んだか」ではなく、「どの施設まで警備できる状態になったか」に注目すると、状態数は \(2^M\) 通りしかありません。

ビットマスクで施設集合を表す

各施設に対して 1 ビットを割り当てます。

• 施設 \(1\) をビット \(0\)
• 施設 \(2\) をビット \(1\)
• …
• 施設 \(M\) をビット \(M-1\)

とすると、たとえば \(M=4\) のとき

• 0000 : まだ何も警備できていない
• 0101 : 施設 \(1,3\) を警備できている
• 1111 : すべての施設を警備できている

というように表せます。

各警備会社 \(i\) についても、「その会社が警備できる施設の集合」を 1 つのビットマスク \(b_i\) に変換できます。

DP の状態

\(dp[mask]\) を

施設の被覆状態が mask になるように会社を選んだときの最小費用

とします。

初期状態は、何も選んでいないので

• \(dp[0] = 0\)

です。

会社 \(i\) を追加で契約すると、現在の被覆状態 mask は

• mask | b_i

に変わります。
ここで | はビット OR です。
つまり、「今まで警備できていた施設」と「会社 \(i\) が新たに警備できる施設」をまとめた状態になります。

したがって遷移は

\[ dp[mask \mid b_i] = \min(dp[mask \mid b_i],\ dp[mask] + C_i) \]

です。

なぜこれで最小値が求まるのか

各会社について「使う / 使わない」を順番に反映していけば、最終的にすべての選び方が考慮されます。
その中で各 mask に対して最小費用だけを持っておけばよいので、DP で解けます。

不可能判定

そもそも全会社を合わせても警備できない施設があるなら、答えは \(-1\) です。
コードでは、全会社の被覆集合を OR した total_cover を使って

• total_cover == full かどうか

を確認しています。

ここで full = (1 << M) - 1 は「全施設が警備できている状態」です。

アルゴリズム

1. 入力を受け取る。
2. 各警備会社について、警備できる施設集合をビットマスク cover[i] に変換する。
3. 全会社の OR を取り、すべての施設をカバーできないなら -1 を出力して終了する。
4. dp[mask] を「状態 mask を作る最小費用」として初期化する。
   • dp[0] = 0
   • それ以外は十分大きい値 INF
5. 各会社 (C_i, cover[i]) について、すべての mask に対して
   • nmask = mask | cover[i]
   • dp[nmask] = min(dp[nmask], dp[mask] + C_i) と更新する。
6. 最終状態 full の値が答え。

例

たとえば \(M=3\) で、現在 mask = 010（施設 2 だけ警備済み）とします。
ある会社が施設 1,3 を警備できるなら、その会社のマスクは 101 です。

この会社を契約すると

\[ 010 \mid 101 = 111 \]

となり、3施設すべてを警備できる状態になります。

計算量

• 時間計算量: \(O(NM + N2^M)\)
• 空間計算量: \(O(2^M)\)

\(M \leq 18\) なので、\(2^M \leq 262144\) です。
したがって \(N \leq 50\) でも十分高速に動作します。

実装のポイント

• 各会社の警備可能施設をビットマスクに変換すると、集合の併合を | 演算だけで高速に行えます。

• INF は十分大きい値にします。今回の最大費用は高々 \(50 \times 10^9\) なので、10**30 なら安全です。

• コードでは DP を 1 次元配列で持っています。
  これはメモリ節約のためで、2 次元 DP にしなくても正しく動きます。

• 同じ会社を2回使うことはできませんが、この遷移では問題ありません。
  なぜなら、一度その会社を使った後にもう一度使っても $\( (mask \mid b) \mid b = mask \mid b \)$ となって状態は変わらず、費用だけ増えるからです。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    C = [next(it) for _ in range(N)]
    cover = []
    total_cover = 0

    for _ in range(N):
        mask = 0
        for j in range(M):
            if next(it):
                mask |= 1 << j
        cover.append(mask)
        total_cover |= mask

    full = (1 << M) - 1
    if total_cover != full:
        print(-1)
        return

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

    for c, b in zip(C, cover):
        for mask in range(1 << M):
            cur = dp[mask]
            if cur == INF:
                continue
            nmask = mask | b
            nc = cur + c
            if nc < dp[nmask]:
                dp[nmask] = nc

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

if __name__ == "__main__":
    main()

---

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