燃やす埋める問題についての記事です．

動機

燃やす埋める問題については，一度エントリを書いた のですが，そこにはともかく理解したことを全部書いたので，コンテスト中に参照しても把握するのがたいへん，という状況になってしまっています．そこで，コンテスト中に思い出したい最小限のことだけまとめることにしました．

考え方

  • 問題文中に「$p$ のとき$b$を受け取る」という記載があったら，「先に $b$ を受け取る．$\neg p$ の時 $b$ を支払う」と読み替えて，すべて支払いをすると考える．
  • グラフ全体の source ノードのラベルは True，sink ノードのラベルは False．
  • ノード $p$ からノード $q$ への矢印に，重み $a$ がついているのは，「$p$が成り立つのに$q$が成り立たない場合，コスト $a$ を支払う」と読む．
  • したがって，この図では，以下が表現されている
    • $p_6$ が成り立って，$p_7$ が成り立たなかったら，$a_2$ 支払う．
    • $p_1$ が成り立たなかったら，$a_5$ 支払う．
    • $p_7$ が成り立ったら，$a_3$ 支払う．
    • $p_8$ は成り立つ．
    • $p_9$ は成り立たない．
  • 最小カットが，コスト最小の真偽割当．図の赤線だと，$p_1, \ldots, p_6, p_8$ を真，$p_7, p_9$ を偽にする割当に相当し，この場合のコストは$a_2 + a_6$．
  • 連言や選言のノードは，矢印を出せるか入れられるかが決まっている．下図を参照．不可の理由は，たとえば連言なら，$p$, $q$を真に，$p\land q$ を偽にできてしまうから．(矢印の根本を真にできてしまうと不当な利益がある．矢印の根本を偽にできても嬉しくない)
  • したがって，「$p \land q$ なら，支払を行う」は，表現できない． しかし，$\neg q$ の方を表すノード $r$ を用意すれば， 「$p$ が成り立って $r$ が成り立たなければ，支払を行う」の形で表現できる．