ABC 142 E - Get Everything

• 問題
• AC
• AC (ゼータ変換)

$N$が小さいので、$dp[S] =$ 集合$S$に含まれる宝箱を全部開けられるような鍵の選び方をした時の最小コスト、を目指したくなる。（不可能な場合は$\infty$。）

${\mathcal O}(2^NM)$のDP

鍵$i$で開けられる宝箱の集合を$C_i$とするとき、$dp[\empty] := 0$と初期化して

$dp[S \cup C_i] := \min (dp[S \cup C_i], dp[S]+C_i)$

をすべての鍵と集合について更新して求まるなら話は早い……が、これは集合の包含関係について全部処理しているわけではない。つまり、この方法で最終的に求まるのは$dp[S] =$ 集合$S$に含まれる宝箱を全部開けられて、$S$に含まれない宝箱を一つも開けられないような鍵の選び方をした時の最小コスト、である。しかし、もう少し考えると、求めるのは全体集合に対する最小コストだったので、それでも問題ないことがわかる。¹

コンテスト中はこの辺の理解にぱっと至らなくて、しばらく逡巡してしまった。

${\mathcal O}(3^N + M)$のDP

最初に目指した$dp$を直接求める方法を考えてみる。$dp$をすべて$\infty$に初期化して、

$dp[\emptyset] := 0$

$dp[C_i] := a_i$

とする。（重複する場合は小さい方を選ぶ。つまり、正確には$dp[C_i] := \min (dp[C_i], a_i)$。）$dp$を上位集合に関してゼータ変換すると、$dp[S] =$ 宝箱の集合$S$を一つの鍵で開ける場合の最小コスト、になっている。あとは、

$dp[S] := \min_{T \subseteq S}(dp[T]+dp[S \setminus T])$

を使って順次最小値を確定していけばよい。部分集合の効率的な列挙のやり方は https://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966 に書いてある。

---

1. 何個か宝箱の集合クエリを受け取ってそれに対する最小コストを返す問題の場合は、最後に$dp$をゼータ変換すればよい。 ↩︎