目次
燃やす埋める問題
競技プログラミングにおける、以下のようなパターンの問題の総称。
問題設定(例題)
$a_1,a_2,...,a_N$ の $N$ 個の廃棄物がある。全て燃やすか埋めるかして処分する。それぞれにコストがかかる。
| $a_1$ | $a_2$ | … | $a_N$ | |
|---|---|---|---|---|
| 燃やすコスト | 50 | 60 | … | 130 |
| 埋めるコスト | 100 | 120 | … | 90 |
さらに「$a_1$ を燃やして $a_2$ を埋めると罰金100円」など、2つの処分方法の組合せによる追加条件がいくつかある。
かかるコストを最小化せよ。
類似概念
近い概念に、PSP（Project Selection Problem）というのがある。
また、QUBO（Quadratic Unconstrained Binary Optimization、制約なし二次形式二値変数最適化）というのもある。
どれも「一番シンプルな問題設定」といったら上のような例題になるけど、どの辺まで応用された問題を扱うかが微妙に異なるっぽい（あまり詳しくないけど）。
まぁ「燃やす埋める問題」は競プロ界隈のローカルネームであり、より一般化された/応用的な内容を学んでいきたい場合は上の名前で調べていけばいいと思う。
ただ、最初の取っかかりとして興味をそそられる名前だし思い出しやすいのでこれはこれでいいと思う。
解き方
追加条件が無ければ単純に $a_1 ... a_N$ についてコストの安い方を選べば良いだけだが、 追加条件があるためにあちらを立てればこちらが立たずで手に負えなくなる。
与えられた条件をグラフで上手く表すことで、最小カット問題として表現することができる。
ただし、追加条件次第で解けないことがある。この解法で解ける条件と解けない条件は後述する。
グラフ化
カットの定義
グラフの「カット」とは、グラフの各頂点（廃棄物）を2つのグループ $S$（燃やす）と $T$（埋める）に振り分けること。
そしてカットのコストとは、$(Sに属する頂点)→(Tに属する頂点)$ に張られている辺のコストの合計のことを指す。
全ての頂点を $S$ や $T$ にすると自明にカットコストが0になってしまうので、 通常、必ず $S$ の頂点 $s$ と必ず $T$ の頂点 $t$ を決めるか、仮想的に追加する。
s -- 10 -→○-- 20 -→○ 30｜ ↑ 50｜ こんなグラフがあったとして ↓ 40｜ ↓ ○-- 60 -→○-- 70 -→ t s -- 10 →[T]-- 20 →[S] 30｜ ↑ 50｜ こう分けた場合、カットのコストは ↓ 40｜ ↓ 10 + 40 + 50 + 70 = 170 [S]-- 60 →[S]-- 70 -→ t
この定義の中で、元の問題を、カットのコストを最小化する問題に上手く落とし込めるよう、グラフを構築していく。
燃やす・埋める単独のコスト
まず、追加条件の無い、単独の燃やすコストと埋めるコストだけを考えると、以下のようなグラフになる。
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やすコスト | 50 | 60 | 130 |
| 埋めるコスト | 100 | 100 | 100 |
,-- 100-→ a1 --- 50---,
燃 | ↓ 埋
や s - 100-→ a2 --- 60-→ t め
す | ↑ る
`-- 100-→ a3 -- 130---'
$a_1$ を燃やすコスト50が、$s$ から遠い右の辺のコストになっているのが少し慣れが必要だが、 「$a_1$ が $S$ グループの場合にカット対象となる辺は右辺」なので、このようになる。
単にここまでの状態だと、各頂点は小さい方の辺がカット対象となるように属するグループをそれぞれ独立に選べばよい。
,-- 100-→ [S]a1 --- 50---,
燃 | ~~ ↓ 埋
や s - 100-→ [S]a2 --- 60-→ t め
す | ~~ ↑ る
`-- 100-→ [T]a3 -- 130---' 50+60+100 = 210
~~~
追加のコスト
ここに「$a_2$ を燃やし $a_3$ を埋めると罰金120」という条件を追加するには、$a_2→a_3$ の辺を追加する。
こうすると、追加した辺もカット対象となる。
,-- 100-→ [S]a1 --- 50---,
燃 | ~~ ↓ 埋
や s - 100-→ [S]a2 --- 60-→ t め
す | ｜120 ~~ ↑ る
| ↓~~~ |
`-- 100-→ [T]a3 -- 130---' 50+60+100 + 120 = 330
~~~
こうなると、そもそも $a_3$ も燃やした方が安くなる。
,-- 100-→ [S]a1 --- 50---,
燃 | ~~ ↓ 埋
や s - 100-→ [S]a2 --- 60-→ t め
す | ↓120 ~~ ↑ る
`-- 100-→ [S]a3 -- 130---' 50+60+130 = 240
~~~
これが罰金を考慮した最小コストとなる。
禁止の制約
制約が「$a_2$ を燃やすと、$a_3$ を埋めてはいけない」という禁止の形になっている場合、 コストを無限大（他のコストを全て合わせても取り得ないような非常に大きな値）に設定しておくとよい。
,-- 100-→ a1 --- 50---,
燃 | ↓ 埋
や s - 100-→ a2 --- 60-→ t め
す | ↓∞ ↑ る
`-- 100-→ a3 -- 130---'
最小カットを解く
最小カットは、辺のコストを容量と見て $s→t$ 間の最大流と一致するという定理があるので、最大流問題として求められる。
制約
賞金（負のコスト）はそのままではダメ
最小カットは、結果的に最大流で解くので、負辺があると上手くいかない。（最大フロー最小カット定理）
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やす | 50 | 60 | -130 |
| 埋める | -100 | 100 | -100 |
-100は100円もらえる（負のコスト）、なんて時は、どうやって辺のコストを設定するか。
全て良い方を選んだと仮定
全て良い方の選択肢を選び、もらえるお金はもらった上で、そこからの差分を「コスト」と見なす。
たとえば $a_1$ は $100$ 円、$a_3$ は $130$ 円をあらかじめもらったと仮定。その上で差分をコストとすると、
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やす | 150 | 60 | 0 |
| 埋める | 0 | 100 | 30 |
となり、負のコストが消える。あとは、最小カットの結果から230を引いたものが本来のコストとなる。
実際の問題では、「コストを最小化せよ」でなく「得点を最大化せよ」という形で問われることも多い。
最大値を求めるのに、最小カット問題に言い換えて、それを最大流で解く、という構造がややこしいが、
まぁ最大流で解く部分はライブラリに流せば終わりなのであまり意識せずともよくて、
元の問題を最小カット問題に置き換える部分に注力する。
「どちらも燃やしたときに罰金」はダメ
「$a_1$ と $a_2$ を同時に燃やすと罰金」など、2つの頂点を同じグループに属させた際に正のコストが課される条件は、表現できない。 （「最大カット問題」となり、NP困難らしい）
ただし追加条件次第で、工夫すれば解ける場合がある。
意味合いを一部反転させる
$S$ を「燃やす」、$T$ を「埋める」と対応づけたのは勝手な都合であって、たとえば
- $a_1$ にとっては $S$ は燃やす、$T$ は埋めるを表す
- $a_2$ にとっては $S$ は埋める、$T$ は燃やすを表す
としても問題ない。
すると、カット対象の辺を張ることができるようになる。
,-燃- 100-→ a1 --- 50-埋-, | ↓100 ↓ a2の左右を入れ替えると、 s 埋- 60-→ a2 ---100-燃→ t 両方燃やすことに対する追加条件の辺を張れる | ↑ `-燃- 100-→ a3 -- 130-埋-'
ただ、例えばこれに加えて「$a_1$ と $a_3$ を同時に燃やすと罰金」「$a_2$ と $a_3$ を同時に埋めると罰金」という条件が重なってしまうと、 どうしてもどれかの組は同じグループに属さざるを得なくなり、カット対象の辺を張ることが不可能になる。
あくまで追加条件次第ということになる。
どういう場合にこの方法が使えるか、というと、追加条件が以下のようになる場合となる。
- 頂点全体を（カットとは別に）以下を満たすように2つの集合 $A,B$ に分けることができる
- 「$a_i$ と $a_j$ が同じグループだと正のコスト」という追加条件は、必ず $a_i,a_j$ のどちらかが $A$ でどちらかが $B$
- 「$a_i$ と $a_j$ が異なるグループだと正のコスト」という追加条件は、必ず $a_i,a_j$ はどちらも $A$ か、どちらも $B$
この場合、集合 $B$ だけ、燃やすと埋めるの意味するグループを入れ替えればよい。
まず前者の追加条件だけを見て、それぞれの $a_i,a_j$ 間に辺を張ったグラフが、二部グラフとなっていればよい。
加えて後者の追加条件もある場合は、二部グラフに分けた上で矛盾しないか調べればよい。
一例として、グリッドで、隣接するマスと同じグループならペナルティが発生するルールで得点を最大化、みたいな問題では、 隣り合うマス同士を結ぶグラフ（グリッドグラフ）は必ず二部グラフとなるので、この方法が可能となることがある。
負のコストなら可
追加条件を「$a_1$ と $a_2$ を同時に燃やすと賞金120円」とすると、可能となる。
この場合、グラフの作り方が変わってくる。追加条件も1つの頂点として表す。
- まず、無条件で120円もらったと仮定
- ダミーノード $b_1$ を追加。燃やしてもコスト0、埋めると120
- $b_1$ を燃やしたなら、必ず $a_1$ と $a_2$ も燃やす
- $b_1→a_1,a_2$ にコスト無限大の辺を追加することで表現
こうすると、グラフは以下のようになる。
,-- 100-→ a1 --- 50--, | ↑∞ ↓ s - 120-→ b1 ---- 0-→ t | ↓∞ ↑ `-- 100-→ a2 -- 60--'
$b_1$ はいわば、$S$ に属するときに「$a_1$ かつ $a_2$ を燃やす」ことを意味するノードと言える。
- $b_1$ を燃やす（$S$ にする）と、
- カット対象は0円の辺となるので、最初にもらった120円はそのまま受け取れる
- $a_1,a_2$ は $T$ にしたら無限大の辺がカット対象となってしまう
- 最小カットを求める上では無限大の辺は避けられるため、$a_1,a_2$ とも $S$ になるはず
- $b_1$ を埋める（$T$ にする）と、
- カット対象は120円の辺となるので、最初にもらった120円は没収
- $a_1,a_2$ については、制約が無くなる
- カット対象辺はあくまで $S→T$ であり、$T→S$ は含まれない
この場合は、頂点が3個以上でもよい。賞金を得るために同時に満たさなければならない頂点全てに辺を張るとよい。
- 「$a_1,a_2,a_3$ を同時に燃やすと賞金」→「$b_1$ から $a_1,a_2,a_3$ にコスト∞の辺」
また、追加条件が逆に「$a_1$ と $a_2$ を同時に埋めると賞金120円」だった場合は、辺の張り方は以下のようになる。
,-- 100-→ a1 --- 50--, 変わった点 | ↓∞ ↓ ・b1の左右が逆転 s --- 0-→ b1 -- 120-→ t ・b1と、a1,a2 間の辺の方向が逆転 | ↑∞ ↑ `-- 100-→ a2 -- 60--'
まとめ
$S=$ 燃やす を「最大流に帰着する場合の起点側」、$T=$埋める を「終点側」とする。
| 条件 | 辺の張り方 |
|---|---|
| $a_i$ を燃やすと罰金 $P$ | $a_i$ から $t$ にコスト $P$ の辺 |
| $a_i$ を埋めると罰金 $P$ | $s$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ を燃やし、$a_j$ を埋めると罰金 $P$ | $a_i$ から $a_j$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も燃やすと、罰金 $P$ ※ただし$a_i,a_j$は二部グラフ上の別グループの頂点 | いずれかの選択肢を反転（$a_j$ とする） $a_i$ から $a_j$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も埋めると、罰金 $P$ ※ただし（同上） | いずれかの選択肢を反転（$a_j$ とする） $a_j$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も燃やす/埋めると、罰金 $P$ ※特に二部グラフなどの特徴の無い制約 | 基本的に無理 |
| $a_i,a_j,...$ を全て燃やすと、賞金 $P$ | あらかじめ $P$ もらう ダミーノード $b$ を追加 $s→b$ にコスト $P$, $b→t$ にコスト $0$ の辺 $b$ から $a_i, a_j, ...$ にコスト $\infty$ の辺 |
| $a_i,a_j,...$ を全て埋めると、賞金 $P$ | あらかじめ $P$ もらう ダミーノード $b$ を追加 $s→b$ にコスト $0$, $b→t$ にコスト $P$ の辺 $a_i, a_j, ...$ から $b$ にコスト $\infty$ の辺 |
上に無い条件でも、他の制約次第で工夫の余地はあるようだ。（もちろんどうしても無理なものもある）
グラフ構築の考え方
グラフを構築する際、どっちからどっちの頂点へ辺を張ればよいか、混乱しやすい。
これまで、グラフ理論におけるカットの考え方から「各ノードをどちらのグループに属させるか」で考えてきた。
- ノード主体の考え方
- 全てのノードを $S$ グループ と $T$ グループ に分ける
- $u$ が $S$ に属し、$v$ が $T$ に属している場合にコストが発生する場合、$u→v$ に辺を張る
一方で、最小カット問題は「$s-t$ 間にフローが流れないように辺を切る」問題とも言えるので、 辺を主体にして「この辺を切ることが、『燃やす』を選択すること」と意味合いづけて、グラフを構築していくことも可能である。
- リンク主体の考え方
- $a_1$ を燃やして $a_2$ を埋めたらコストが発生する場合、それぞれに該当するリンクを切っても $s→t$ のフローがまだ途切れていない状態にするように辺を張る
やってることは同じでも、考え方を変えるだけで実際の問題からのグラフ構築のしやすさが異なってくる、かも。
ノード主体の場合、単独で燃やす・埋める際のコストが $s,t$ の意味合いと左右逆転するところが少し直感に反するものの、 それ以外の、追加条件の部分では、リンク主体よりも直感的に張れる気がする。
バリエーション
工夫次第でいろいろできるらしい
3択の選択肢
- 問題設定
- 「燃やす」「埋める」に、「何もしない」の選択肢が追加される
- 制約条件は、「Xを燃やしてYを埋めると罰金P」という形式のみ
選択肢を増やすだけならノードを複製して横に繋ぐことも考えられるが、これだと制約条件の辺が上手く追加できなくなる。
ダメな例 ,-- 50→ a11 --100→ a12 -- 0 --, | ↓ s -- 60→ a21 --100→ a22 -- 0 -→ t | ↑ `- 130→ a31 --100→ a32 -- 0 --'
3択を無理矢理2択にする。簡単のため、1つの廃棄物 $A$ についてだけ考える。
| $A$ | |
|---|---|
| 燃やす | 100 |
| 埋める | 50 |
| 何もしない | 80 |
そして、頂点を２分割し、グループ $S,T$ を以下のように意味づける。
- $A_1$ にとって、$S$ は「燃やす」、$T$ は「何もしない(1)」
- $A_2$ にとって、$S$ は「何もしない(2)」、$T$ は「埋める」
下図ようにグラフを作る。
,-- 80→ A1 -- 100--, s ↓∞ t `-- 50→ A2 --- 80--'
「燃やす」と「埋める」を同時に行うのは矛盾なので、$A_1$ が $S$ で $A_2$ が $T$ となることがないよう、$A_1→A_2$ へ無限大の辺を張る。また、
- 「燃やす」と「何もしない(2)」が選ばれた場合、燃やす
- 「何もしない(1)」と「何もしない(2)」が選ばれた場合、何もしない
- 「何もしない(1)」と「埋める」が選ばれた場合、埋める
どの選択肢も余分に「何もしない」を1つだけカットするので、あらかじめその分の補償金80円をもらっておく。
この場合、$A_1,A_2$ とも $T$ に属させるのが最小となり、埋めるのがよいとわかる（自明だが）。コストは50+80=130に、あらかじめもらった80を引き、50となる。
廃棄物を2つに増やす。
| $A$ | $B$ | |
|---|---|---|
| 燃やす | 100 | 200 |
| 埋める | 50 | 240 |
| 何もしない | 80 | 500 |
- 制約条件
- $B$ を燃やし、$A$ を埋めると罰金100円
制約条件を加える前のグラフは、このようになる。
,-- 80→ A1 - 100 --, | ↓∞ | |-- 50→ A2 -- 80 --| s t |- 500→ B1 - 200 --| | ↓∞ | `- 240→ B2 - 500 --'
ここで、制約条件を分割後のノードで解釈すると「$B_1$ が $S$ で、$A_2$ が $T$ の場合、罰金が発生する」となる。
それに添うように辺を追加すると、目的のグラフが完成する。
,-- 80→ A1 - 100 --, | ↓∞ | |-- 50→ A2 -- 80 --| s ↑100 t |- 500→ B1 - 200 --| | ↓∞ | `- 240→ B2 - 500 --'
最小カットは
,-- | → [T]A1 - 100 --, | ↓∞ | |-- | → [T]A2 -- 80 --| 80+50+100+200+500 - (80+500) = 350 s ---- t |- 500→ [S]B1 - | --| | ↓∞ | `- 240→ [S]B2 - | --' ,-- | → [T]A1 - 100 --, | ↓∞ | |-- 50→ [S]A2 -- | --| 80+80+200+500 - (80+500) = 280 s ↑100 t |- 500→ [S]B1 - | --| | ↓∞ | `- 240→ [S]B2 - | --'
となり、$A$ は単独なら埋めた方がよいところ、制約条件の追加によって何もしないに変化する。
参考
Project Selection Problemという、似た考え方の解法もある。
劣モジュラ関数という概念を使って、どんな問題なら可能かを説明されている。
