Dungeon（code festival 2014 上海 [H]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

解法

• 鍵に $1,2,\dots ,n$ の番号をつけておきます。
  宝箱に、$1,2,\dots ,m$ の番号をつけておきます。

まず、鍵は、宝箱を開けるときに拾いに行くとしてよいです。鍵の所持数などは考える必要がなくなり、どの鍵と宝箱を組み合わせるかだけを考えればよくなります。

このとき、「鍵 $i$ で宝箱 $j$ を開けることによる利得」が計算できます。

• 鍵 $i$ の取得のための支出
• 防御力の増加に、$max(i,j)$ よりも右にいるモンスターの数をかけた値が利得

を計算すればよいです。同じ鍵や箱を $2$ 回とることはできないので、本問題は最大重みマッチングを求める問題として定式化できました。

なお、利得が負の組合せがありますが、この組合せの利得を $0$ と再定義しておけば、必ず $min(n,m)$ のマッチングを作る場合に限定してもよいです。

---

密な二部グラフの最大重み完全マッチングは、ハンガリアン法などによって $O(min(n,m)nm)$ 時間で解くことができて、AC が得られます。

参考：https://judge.yosupo.jp/problem/assignment