AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC142 E - Get Everything

問題原文

atcoder.jp

問題要旨

 N 個の宝箱があり、 宝箱  i を開けるためには、鍵  i が必要になる。
また、 M 個の鍵セットが売られており、  j 番目の鍵セットは  a_j 円で、  b_j 個の鍵のセット  c_{j1}, c_{j2}... を販売している。
鍵が何度でも再利用できるとき、全ての宝箱を開けるのに必要な最小の金額はいくらか?

  •   1 \leq N \leq 12
  •   1 \leq M \leq 10^{3}
  •   1 \leq a_i \leq 10^{5}
  •   1 \leq b_i \leq N
  •   1 \leq c_{ij} \leq N

解法

bitDP。(というか制約がbitDPをやれと言っている。。。)
 dp[bs :=] (鍵の集合  bs を手に入れるために必要な最小金額) として、 dpテーブルを埋めておけばOK。
遷移元は直前のみなので、  i 番目までみた時に〜はいらない。(1次元ナップサックと同じですね)

実装

or演算を使うと楽。
あと、入力で与えられる鍵の集合は整数にエンコードしておこう。

N, M = map(int, input().split())
keys = []
for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (c - 1) for c in list(map(int, input().split()))])
    keys.append([a, c])


# dp[bs] := 鍵の集合bsを手に入れるのに必要な最小費用
dp = [float('inf')] * (1 << N)
dp[0] = 0

for cost, key in keys:
    for bs in range(1 << N):
        dp[bs | key] = min(dp[bs | key], dp[bs] + cost)

print(dp[-1] if dp[-1] != float('inf') else -1)

感想

いい典型。
巡回セールスマン問題よりも、bitDPの教材としては優れてそう。