燃やす埋める問題の自己流まとめ

短い版を[こちら](https://yamate11.github.io/blog/posts/2021/05-22-burn-bury/) に書きました．

## 背景
ネットワークフローを勉強してみよう，と思っていたところで，グラフの最小カット問題に行き当たりました．診断人さんの[『最小カットを使って「燃やす埋める問題」を解く』](https://www.slideshare.net/shindannin/project-selection-problem) というスライドがたいへん親切にわかりやすく書かれていて，勉強になりました．ただ，「考えて選択肢の順番を決めないといけない」(スライド35) というところが難しく感じました．

次に，よすぽさんのblog記事[「最小カットについて」](http://yosupo.hatenablog.com/entry/2015/03/31/134336) を読みました．最小カットで解ける問題とは，要するに次のタイプだ，というまとめに，なるほど，と思いました．

> * 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない
> * 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する
> * 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある
> * 罰金の最小値は？

ただ，その記事の後ろに出てきますように，「Xが赤で、Yが赤の時にZ円の報酬」や「Xが青で、Yが青の時にZ円の報酬」も扱えるわけです．もちろんその記事に詳述されているのですが，自分なりの理解をしたいな，と思い，以下のように整理しました．

本質的には，お二人の説明と何も変わっているところはありませんが，自分としては，問題への適用方針がはっきりできたような気がしています．

## 一般形

次の形をしている問題が，最小カットによって解ける燃やす埋める問題です．

* ある条件が満たされたときに (正の量を) 支払う．ある条件が満たされたときに (正の量を) 受け取る．支払を最小 (あるいは受取りを最大) にせよ，という形で問題が規定されている．
* 適当な命題の集合 $P_0$ が，以下の条件を満たすように定義できる．
* $P_0$ は，True (真) と False (偽) を含む．
* 「支払う」タイプの条件は，$Q \subseteq P_0$ と $R \subseteq P_0$ を使って，「$Q$のうち1つ以上が成り立ち，しかも，$R$のうち1つ以上が成り立たない」と記述できる．論理式で書けば，$\bigvee_{q \in Q} q \land \bigvee_{r \in R} \neg r$ となる．
* 「受取る」タイプの条件は，$Q \subseteq P_0$ と $R \subseteq P_0$ を使って，「$Q$のすべてが成り立つか，または，$R$のすべてが成り立たない」と記述できる．論理式で書けば，$\bigwedge_{q \in Q} q \lor \bigwedge_{r \in R} \neg r$

ただし，$Q$, $R$ は空ではないことにします．

$P_0$ をうまく決定できれば，あとは後述する方法に従って機械的に解ける，ということになります．

## 良く現れる形

一般には，$Q$ と $R$ を使って上のように表現できますが，頻出するのは次の形かと思います．
$p$, $q$ を $P_0$ の命題とします．

### 支払う条件

* p が成り立つ  ($p$)
* p が成り立たない   ($\neg p$)
* p が成り立ち，q が成り立たない   ($p \land \neg q$)
* p か q の少なくとも一方が成り立つ   ($p \lor q$)
* p か q の少なくとも一方が成り立たない   ($\neg p \lor \neg q$)

### 受取る条件

* p が成り立つ  ($p$)
* p が成り立たない   ($\neg p$)
* p が成り立たないか，q が成り立つ   ($\neg p \lor q$)
* p と q の両方が成り立つ   ($p \land q$)
* p か q の両方が成り立たない   ($\neg p \land \neg q$)

たとえば，支払う条件の一般形で，$Q = \\{p\\}$, $R = \\{False\\}$ としますと，1番目に挙げた「pが成り立つ」が得られますし，$Q = \\{True\\}$, $R = \\{p, q\\}$ としますと，5番目に書いた「pかqの少なくとも一方が成り立たない」が得られます．

## 適用例．その1

### MUL

AtCoder Regular Contest 085 の [問題E. MUL](https://atcoder.jp/contests/arc085/tasks/arc085_c) です．表現しなければならない規程は以下の通りです．

* $i$ が $j$ の約数である時，宝石 $i$ を割ったら，宝石 $j$ を割らなければならない．
* $a_i > 0$ なる $i$ について，宝石 $i$ が割られなければ，$a_i$ 受取る．
* $a_i < 0$ なる $i$ について，宝石 $i$ が割られなければ，$- a_i$ 支払う．

使用する命題の集合 $P_0$ は，次の命題の全体とします．

* $p_i$ ... 宝石 $i$ を割る．

すると，3つの規程が，前節の条件を満たすように表現できます．

* $i$ が $j$ の約数であるような$i$, $j$ に対し，「$p_i$ が成立して $p_j$ が成立しない」とき，$\infty$ 支払う．
* $a_i > 0$ なる $i$ について，「$p_i$が成り立たない」とき，$a_i$ 受け取る
* $a_i < 0$ なる $i$ について，「$p_i$が成り立つ」とき，$-a_i$ 支払う

### FoxAndGo3

診断人さんのスライド 36～54 でとり上げられている問題です．そこでは，うまくいくグラフと，そうでないグラフが説明されています．

$P_0$を，次の命題全体とします．

* $p_{ij}$ ... 位置 $(i, j)$ に黒を置く
* $q_{ij}$ ... 位置 $(i, j)$ の白を取り除く

すると，次のように条件が書けます．

* 何も置かれていない位置 $(i, j)$ について，
    * $p_{ij}$が成り立つとき1支払う
    * $p_{ij}$が成り立たないとき1受け取る
* 白石が置かれている位置 $(i, j)$ について，
    * $q_{ij}$が成り立つとき1受け取る
    * $(i,j)$ の隣接4点 (この問題では，隣接4点には白はないと仮定されている) のうち，何も置かれていない点 $(x, y)$ について，$q_{ij}$が成立して $p_{xy}$が成立しなければ，$\infty$ 支払う．

これでうまく表現できました．注意すべき点としては，$P_0$ を次のように定めたのではうまくいかない，ということがあります．

* $p_{ij}$ ... 位置 $(i, j)$ に黒を置く
* $q'_{ij}$ ... 位置 $(i, j)$ の白を置いたままにする．
 
こうしますと，最後の規程に現れる条件が，「$q'\_{ij}$と$p\_{xy}$がともに成立しないならば」となってしまいます．これは，受取りの条件としては正当ですが，支払の条件に使うことはできません．

## グラフの構成

まず，問題を言い換えて，受取りに関する規定「条件Aが成り立てばB受取る」を，「条件Aが成り立たなければ，B支払う」に変更します．あらかじめ B を受取っておいてこの新たな規程を適用するのと，もとの問題は同じ事になります．したがって，言い換えた後の問題を解いて，結果に Bを加えれば良いです．ここで，受取りの条件が満たすべき形の否定を作ると，支払の条件が満たすべき形になっていることに注意してください．

グラフを構成します．まず，$P_0$ の各要素に対応するノードを作ります．つぎに，各支払規程を見ます．条件は，$Q$ と $R$ を使って表されています．支払額を$C$とします．

* 新しいノード $u$ と $v$ を作る．
* $Q$ の各要素に対応するノードから，$u$ へ，容量$\infty$の辺を張る．
* $v$ から $R$ の各要素に対応するノードへ，容量$\infty$の辺を張る．
* $u$ から $v$ へ，容量$C$の辺を張る．

ただし，$Q$ や $R$ が単元集合の時には，$u$ や $v$ を作るのを省略して，その単元自身を用いるものとします．

ノードTrueとFalseの最小カットが，もとめる最小値になっています．

## 正当性

以下の2つを示します．

1. $P_0$への任意の真偽値割り当てに対し，その時の支払額が最小カット以上であること
2. 支払額が，最小カットと等しくなるような$P_0$の真偽値割り当てがあること

まず，1.です．ノードは，$P_0$ の要素に対応しているか，または，規程の条件 $Q$, $R$ に対応しているかのいずれかです．ノードの集合$U$ を，つぎのノードの全体と定義します．

* ノードが$P_0$の要素に対応しているときには，その対応している要素に真が割り当てられている
* $Q$に対応しているときには，$Q$の要素の少なくともひとつに真が割り当てられている
* $R$に対応しているときには，$R$の要素のすべてに真が割り当てられている

$V$ は，$U$ に属さないノードの全体とします．すると，$(U, V)$ は，True-False カットであり，支払額がこのカットの値となることが確認できます．

次に2.です．最小カット$(U_0, V_0)$ をとり，$P_0$ に対する真偽値割り当てとして，$p \in P_0$ に対応するノードが $U_0$ に属しているときに真，そうでないときに偽とするものを取ります．このときの支払額 $C'$ がカットの値 $C_0$ と一致することを言います．帰謬法で，$C_0 \neq C'$ としましょう．1.より，$C_0 < C'$ です．特に $C_0 < \infty$ です．すると，規程に現れる$Q$と$R$の組で，$Q$がすべて偽で，$R$がすべて真になっているものであって，この$Q$と$R$に対応するノード$s$と$t$について，$s \in U_0$, $t \in V_0$ となるものが存在しなければなりません．なぜなら，そのようなものが無いとすると，グラフ上の有限容量の辺でカットの値に寄与できるものは，$Q$ のうち一つ以上が真で，$R$のうち一つ以上が偽のものだけですが，そのようなものを全部集めても $C'$ しかないからです．さてこの場合，カット $(U_0 - \\{s\\}, V_0 \cup \\{s\\})$ を考えると，カット $(U_0, V_0)$ よりも真に値が小さくなってしまいます．矛盾が導かれました．


## 適用例．その2


### The Year of Code Jam

診断人さんのスライド 56～68 でとりあげられている問題です．

今度は，次の命題を考えてもうまくいきません:

* $p_d$ ... 日付 $d$ のマスを青にする．

条件を書くと，次のようになってしまいます．

* 「?」が書かれている日付 $d$ に対し，「$p_d$が成立すれば，4受け取る」
* 隣接する日付の組 $(d, e)$ に対し，「$p_d$が成立し，$p_e$も成立すれば 2 支払う」

前者は適用可能な条件ですが，後者はそうではありません．

そこで，診断人さんのスライドにあるのと同じ工夫をすることになります．命題を次のようにします．

* $p_d$ ... 日付 $d$ が奇数マスかつ青であるか，偶数マスかつ白であるかのいずれかである．

この言い換えによって，条件は以下のようになります．

* 「?」が書かれている奇数マス日付$d$について，「$p_d$が成立すれば，4受け取る」
* 「?」が書かれている偶数マス日付$d$について，「$p_d$が成立しなければ，4受け取る」
* 隣接する日付の組 $(d, e)$ に対し，「$p_d$が成立し，$p_e$が成立しなければ 2 支払う．」(ただし，奇数マスに入っている方を$d$とする)

これで問題が最小カットに帰着できました．


### Surrounding Game

診断人さんのスライド70～84です．

マス$v$に隣接するマスの集合を $N(v)$ と書きます．命題をまず次のように考えてみます．

* $p_v$ ... マス$v$に石を置く．

すると，条件は以下のようになります．

* $b_v - c_v > 0$のとき，$p_v$ が成り立てば，$b_v - c_v$ 受け取る．
* $b_v - c_v < 0$のとき，$p_v$ が成り立てば，$c_v - b_v$ 支払う．
* $p_v$ が成り立たず，すべての $w \in N(v)$ に対して $p_w$ が成り立つならば，$b_v$ 受け取る．

3番目の条件は，前節に書いた形と似ているようにも見えますが，残念ながら，肯定と否定が混じっています．さきほどの The Year of Code Jam と同じように，奇数マスと偶数マスでyes/noを入れ換えればうまくいきます．

* $p_v$ ... $v$が奇数マスでありかつ石を置かれているか，または，$v$が偶数マスでありかつ石が置かれていない．

条件を書き直します．

* $b_v - c_v > 0$となる奇数マス$v$について，$p_v$ が成り立てば，$b_v - c_v$ 受け取る．
* $b_v - c_v > 0$となる偶数マス$v$について，$p_v$ が成り立たなければ，$b_v - c_v$ 受け取る．
* $b_v - c_v < 0$となる奇数マス$v$について，$p_v$ が成り立てば，$c_v - b_v$ 支払う．
* $b_v - c_v < 0$となる偶数マス$v$について，$p_v$ が成り立たなければ，$c_v - b_v$ 支払う．
* 奇数マス$v$ について，すべての $w \in \\{v\\} \cup N(v)$ に対して $p_w$ が成り立つならば，$b_v$ 受け取る．
* 偶数マス$v$ について，すべての $w \in \\{v\\} \cup N(v)$ に対して $p_w$ が不成立ならば，$b_v$ 受け取る．

前節の形になりましたので，最小カットに帰着できます．