燃やす埋める纏める - かんプリンの学習記録

この記事は競プロ Advent Calendar 2022 11日目のために作成されました。

燃やす埋める問題として解ける制約やその他関連情報をまとめました。
他の情報も見つけ次第更新していきます。(最終更新日：2022/12/11)

燃やす埋める問題とは
燃やす埋めるで解ける制約
3つ以上の処理方法がある場合
その他の損失
答えの復元
計算量
ライブラリの作成
練習問題

燃やす埋める問題とは

燃やす埋める問題[1]の元ネタは多分こんな感じです。
「燃やす/埋める」以外にも「白で塗る/黒で塗る」、「使う/使わない」などの選択肢の問題もあります。

燃やす埋める問題
${i}$ 番目のゴミを燃やすとき ${A_i}$ の損失が、埋めるとき ${B_i}$ の損失が発生する。さらに、 ${i}$ 番目のゴミを燃やし ${j}$ 番目のゴミを埋めると追加で ${C_{i,j}}$ の損失が発生する。
すべてのゴミを適切に処理することで損失を最小化せよ。

この制約はグラフカット[2]に帰着され[3]、最小カット(=最大流)が答えとなります。
具体的には、以下のようなグラフを作り、 ${s}$ - ${t}$ カット ${(S,T)}$ のうち最小のものを求めればよいです。 ${i\in S}$ のとき、ゴミ ${i}$ を燃やすことに対応し、 ${i\in T}$ のとき、ゴミ ${i}$ を埋めることに対応しています。

カットエッジは赤い頂点から青い頂点への有向辺であり、最小カットは各頂点を赤or青に塗り分けるもののうちカットエッジの重みの和を最小にするようなものになります。この塗り分けが燃やすor埋めるへの割り当てと同じ意味になっています。

この「燃やす埋める」というのは日本の競プロ界隈でしか使われていません。

流行りのChatGPTも知らないみたいです()

「Project Selection Problem」と言う人もいますが、燃やす埋めると問題設定が違うと思います(解ける問題の集合は同じ)[4][5]。

単に「最小カット」としか言ってないような解説も多いです。

燃やす埋める問題として解ける制約

燃やす埋める問題として解ける制約について解説します。
他にもあると思いますが分かる範囲で書いてます。

ゴミ ${i}$ を燃やしたとき ${A_i}$ の損失

${A_i > 0}$ のとき

ゴミ ${i}$ を燃やしたとき ${A_i}$ の損失発生するので、 ${i\in S}$ のときに ${A_i}$ の重みのカットエッジがあるようにグラフを作ればよいです。

そのようなグラフは頂点 ${i}$ から頂点 ${t}$ に重み ${A_i}$ の有向辺を張ることで作ることができます。

${A_i < 0}$ のとき

ゴミ ${i}$ を燃やすと ${A_i}$ の損失 ${\rightarrow}$ 無条件で ${A_i}$ の損失＋ゴミ ${i}$ を埋めると ${-A_i(> 0)}$ の損失
と言い換えることができるので、次に説明する埋めたときと同様に辺を張ることができます。

例

ゴミ ${i}$ を埋めると ${-50}$ の損失が発生する場合、以下のように辺を張ったグラフの最小カットの重みを求め、それに ${-50}$ を加えたものが問題の答えとなります。

ゴミ ${i}$ を埋めたとき ${B_i}$ の損失

${B_i > 0}$ のとき

${i\in T}$ のときカットの重みが ${B_i}$ である ${\Leftrightarrow}$ 頂点 ${s}$ から頂点 ${i}$ に重み ${B_i}$ の有向辺がある。

${B_i < 0}$ のとき

ゴミ ${i}$ を燃やしたとき、 ${A_i(< 0)}$ の損失が発生する場合と同様に考えることができます。

ゴミ ${i}$ を燃やしゴミ ${j}$ を埋めたとき ${C_{i,j}(> 0)}$ の損失

${i\in S}$ かつ ${j\in T}$ のときカットの重みが ${C_{i,j}}$ である ${\Leftrightarrow}$ 頂点 ${i}$ から頂点 ${j}$ に重み ${C_{i,j}}$ の有向辺がある。

${2}$ つのゴミの処理方法による損失

実は[ゴミiを燃やしゴミjを埋めたときCij(> 0)の損失]は一般化できます。
ゴミ ${i}$ とゴミ ${j}$ の処理方法(燃やす、埋める)による損失が以下のように表されるとします。

この損失が ${B+C-A-D\geq 0}$ を満たす場合、以下のように分解することができます。

無条件に ${A}$ の損失
＋ゴミ ${i}$ を埋めると ${C-A}$ の損失
＋ゴミ ${j}$ を埋めると ${D-C}$ の損失
＋ゴミ ${i}$ を燃やし、ゴミ ${j}$ を埋めると ${B+C-A-D}$ の損失

これらはすでに説明した方法でグラフを作ることができます[6][7]。

${3}$ ゴミの処理方法による損失

${3}$ つのゴミの処理方法による損失を考えます。詳しい説明(理由)は他の方の記事[6][7]に任せますが、この損失を表現するには「ゴミ ${i,j,k}$ のうち、 ${1}$ つ以上が燃やされたとき ${C}$ の損失が発生する」という損失を表現する必要があります。

${C > 0}$ の場合について説明します。
これは、新たにグラフに「ゴミ ${i,j,k}$ のうち、 ${1}$ つ以上が燃やされた(※)」ことを表す頂点 ${v}$ を追加し、(※)が真の場合 ${v\in S}$ 、偽の場合 ${v\in T}$ になると考えると、

(※)が偽かつゴミ ${i}$ を燃やすと ${\infty}$ の損失
＋(※)が偽かつゴミ ${j}$ を燃やすと ${\infty}$ の損失
＋(※)が偽かつゴミ ${k}$ を燃やすと ${\infty}$ の損失
＋(※)が真なら ${C}$ の損失

として表すことができます。

複数のゴミのうち ${1}$ つ以上が燃やされたとき ${C(> 0)}$ の損失

ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、 ${1}$ つ以上が燃やされたとき ${C(> 0)}$ の損失がかかることをグラフで表現します。
先程 ${3}$ つのゴミの場合を説明しましたが、これと同様の方法で表現することができます。

複数のゴミのうち ${1}$ つ以上が埋められたとき ${C(> 0)}$ の損失

ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、 ${1}$ つ以上が埋められたとき ${C(> 0)}$ の損失がかかることをグラフで表現します。
先程と同様に考えると以下のように表現することができます。

より複雑な損失

ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ と ${Y=\{y_1,y_2,\dots ,y_{|Y|}\}}$ 、
${A_x > 0(x\in X), B_y > 0(y\in Y)}$ 、
${C > 0}$

が与えられたときに、

${X}$ に含まれるゴミ ${x}$ のうち燃やしたゴミににおける ${A_x}$ の和 ${\sum_{x\in S\cap X}A_x}$
${Y}$ に含まれるゴミ ${y}$ のうち埋めたゴミにおける ${B_y}$ の和 ${\sum_{y\in T\cap Y}B_y}$
${C}$

の最小値 ${\min(\sum_{x\in S\cap X}A_x,\sum_{y\in T\cap Y}B_y,C)}$ が損失となるようなグラフを作ります。

詳細は省略しますが、以下のように新たに頂点 ${u,v}$ を追加し、有向辺を張ればよいです。
これが正しく損失を表現できていることは、任意の ${s}$ - ${t}$ カット ${(S,T)}$ において、このカットエッジの重みが最小となる ${u,v}$ の割り当てを考えることで確認出来ます。
図では ${X\cap Y = \emptyset}$ に見えますが、 ${X\cap Y \neq \emptyset}$ であっても構いません。

( ${u\leftarrow v}$ の ${\infty}$ の辺は張らなくてもいいかも...)

また、

${\min(\sum_{y\in T\cap Y}B_y,C)}$ は ${u=s}$
${\min(\sum_{x\in S\cap X}A_x,C)}$ は ${v=t}$
${\min(\sum_{x\in S\cap X}A_x,\sum_{y\in T\cap Y}B_x)}$ は ${u=v}$

とすることで表現できます。

したがって、上で説明した以下の ${2}$ つはこの損失の特殊な例と考えることができます。
複数のゴミのうち1つ以上が燃やされたときC(> 0)の損失
 複数のゴミのうち1つ以上が埋められたときC(> 0)の損失

他にも、以下のようにこの構造を複数組み合わせるとより複雑な損失を表現することができます。複雑すぎる割にあまりコンテストに出てこなさそうなのでこの記事では説明しませんが、どのような損失を表すのか考えてみてください。

3つ以上の処理方法がある場合

これまでは選択肢が ${2}$ つ([燃やす/埋める])の場合について説明してきました。以下のグラフにおいて、頂点 ${i}$ を赤に塗る( ${i\in S}$ )ことが[燃やす]を選ぶことに対応し、青に塗る( ${i\in T}$ )ことが[埋める]を選ぶことに対応しています。

これを選択肢が ${3}$ つ以上ある場合に拡張します。

ゴミ ${i}$ の処理方法として ${k_i}$ 個の選択肢([処理 ${1}$ /処理 ${2}$ / ${\dots}$ /処理 ${k_i}$ ])があるとします。
以下の条件を満たす頂点 ${i_1, i_2, \dots ,i_{k_i-1}}$ を新たに追加します。

${x=1,2,\dots,k_{i}-1}$ について、

${i_x\in S}$ のとき、[処理 ${1}$ , 処理 ${2}$ , ${\dots}$ , 処理 ${x}$ ]のうちいずれも選ばない。
${i_x\in T}$ のとき、[処理 ${1}$ , 処理 ${2}$ , ${\dots}$ , 処理 ${x}$ ]のうちいずれかを選ぶ。

${i_x\in T\land i_{x+1}\in S}$ となることはないことに注意すると、以下のようなグラフを作ることができます。 ${c_x}$ は処理 ${x}$ を選んだ時の損失です。

${c_x}$ が負の場合でも、無条件で ${C=\underset{1\leq x\leq k_i-1}{\min}c_x}$ の損失を発生させ、 ${c_x\leftarrow c_x - C}$ とすることで ${c_x\geq 0}$ とすることができます。

他にも[8]のように張る方法もあります。

2つのゴミの処理方法による損失

${2}$ つのゴミの処理方法の選択による損失を考えます。以下のように

赤： ${i_1}$ から ${j_1}$ への有向辺
橙： ${i_1}$ から ${j_2}$ への有向辺
緑： ${i_2}$ から ${j_1}$ への有向辺
青： ${i_2}$ から ${j_2}$ への有向辺

が張られたグラフがどのような損失を表しているかを考えます。

損失を表で書くと以下のようになります。辺の色と同じ色の枠の部分には一律に辺の重み分の損失が発生します。

損失をこの形に分解することができればグラフで表すこともできるということになります。例として以下のような損失をグラフで表してみます。

ゴミiを燃やしたときAiの損失やゴミiを埋めたときBiの損失を用いると、行や列から一律に値を引くことができます。

まず、ゴミ ${i}$ に対して[処理 ${1}$ ]を選ぶと ${36}$ の損失が発生することにすると、ゴミ ${i}$ の[処理 ${1}$ ]の行から ${36}$ を引くことができます。同様に[処理 ${2}$ /処理 ${3}$ ]の行についても行います。

ゴミ ${j}$ に対して[処理 ${1}$ ]を選ぶと ${-35}$ の損失( ${35}$ の利得)が発生することにすると、ゴミ ${i}$ の[処理 ${1}$ ]の列から ${-35}$ を引くことができます。同様に[処理 ${2}$ /処理 ${3}$ ]の列についても行います。

先程の色枠の表を見ると、損失が ${2}$ 次元累積和のようになっており、差分を取ることでそれぞれの辺の重みを求めることができます。

このとき、差分を取った値(右表)は非負である必要があります。
非負である条件として、損失の表(左表)内のすべての ${2×2}$ の部分を抜き出し、値を以下のように ${A,B,C,D}$ としたとき ${B+C-A-D\geq 0}$ であることが必要です。

∞の損失の扱い

これで機械的に解けるようになったわけですが、 ${\infty}$ の損失を扱う場合には注意が必要です。ここで以下のような損失を考えてみましょう。

実装の際、 ${\infty}$ を巨大な定数として扱ってしまうと非負条件( ${B+C-A-D\geq 0}$ )が成り立たないためグラフを作ることができません。
しかし、実際には以下のようなグラフによりこの損失を表現することができます。

※これの処理方法について書きたいのですが投稿日に間に合わなさそうだったので後日書きます。

処理方法の決め方

各ゴミの処理方法は自由に決めることができます。[8]
ゴミ ${1}$ は(処理 ${1}$ ,処理 ${2}$ )=(燃やす,埋める)、ゴミ ${2}$ は(処理 ${1}$ ,処理 ${2}$ )=(埋める,燃やす)といったように、各ゴミで処理方法の並びが異なっていても構いません。

これを利用すると以下のような非負条件( ${B+C-A-D\geq 0}$ )を満たさない場合にも[2つのゴミの処理方法による損失]で説明した方法でグラフを作ることができる場合もあります。

${2}$ 部グラフ系の問題でこの変換を使うことがあります。

その他の損失

その他の損失を問題形式でいくつか置いておきます。重要な問題も含まれているので是非解いてみてください。

損失問題 ${1}$
ゴミ ${i}$ とゴミ ${j}$ を燃やすと ${P( > 0)}$ の利得( ${-P}$ の損失)が発生する。

解説

2つのゴミの処理方法による損失のように損失の表を作ります。

これは非負条件 ${0+0-(-P)-0\geq 0}$ を満たすのでコレに従ってグラフを作ることができます。

損失問題 ${2}$
ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、燃やされたゴミの数を ${K}$ とする。このとき、 ${K^2}$ の利得が発生する。

解説

${X}$ に含まれるすべてのゴミのペア ${(x_i,x_j) (1\leq i < j\leq |X|)}$ について、ゴミ ${x_i}$ とゴミ ${x_j}$ を燃やすと ${2}$ の利得が発生するようにします(損失問題 ${1}$ )。

${K}$ 個のゴミが燃やされたとすると ${K(K-1)}$ の利得が発生しますが、さらに ${x_i (1\leq i\leq |X|)}$ についてゴミ ${x_i}$ を燃やした時に ${1}$ の利得が発生するものとすれば、追加で ${K}$ の利得が発生し、全体で ${K(K-1)+K=K^2}$ の利得を表現するとこができます。

一般に、ゴミの集合 ${X}$ および ${w_{x_i} \geq 0}$ が与えられているとき、 ${(\sum_{x\in X\cap S}w_x)^2=\sum_{x\in X\cap S}w_x^2+2\sum_{x_i,x_j\in X\cap S, i < j}w_{x_i}w_{x_j}}$ となるので、 ${(\sum_{x\in X\cap S}w_x)^2}$ は「 ${x_i}$ を燃やすと ${w_{x_i}^2}$ の利得」、「 ${x_i,x_j}$ を燃やすと ${2w_{x_i}w_{x_j}}$ の利得」によって表現できます。

損失問題 ${3}$
ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、燃やされたゴミの数を ${K}$ とする。このとき、 ${K^3}$ の利得が発生する。

解説

損失問題 ${2}$ と同様に考えると3つのゴミの処理方法による損失が必要になってしまい、 ${O(|X|^3)}$ の頂点や辺が追加されてしまいます。これを頂点 ${O(|X|)}$ 、辺 ${O(|X|^2)}$ に抑える方法を説明します。

実は、損失の関数 ${f}$ において ${f(K+1)-f(K)\leq f(K)-f(K-1) (1\leq K\leq |X|-1)}$ が成り立つならばグラフで表現することができます。今回の問題では ${f(K)=-K^3}$ なのでこれが成り立っています。

例として、 ${|X|=7}$ の以下のような関数 ${f}$ を考えます(分かりやすいように折れ線で表しています)。

結論から言うと、この関数は、
${ \begin{array}{ll} f(K)=&\min(K,4)+\min(K,2)+\min(K,1) \\ &+\min(21-3K,6)+\min(7-K,1)-7 \end{array} }$
と分解できます[9]。一般に、この条件を満たす関数 ${f(K)}$ は正整数 ${a,b}$ を用いて ${\min(a×K,b)}$ や ${\min(a×(|X|-K),b)}$ と表されるものの和として表すことができ、これはまさに[より複雑な損失]で説明したようにグラフで表現することができます。

答えの復元

最小カットの重みで求めた後、それぞれのゴミの処理としてどれを選んだかを求めることができます。

[1]で説明されているように、各頂点 ${v}$ が ${v\in S}$ であるか ${v\in T}$ であるかは、 ${v}$ が残余ネットワークにおいて始点 ${s}$ から到達可能であるかどうかで分かります。

計算量

最大フロー最小カット定理[10]より、最小カットを求めるには最大フローを求めればよいです。

${n}$ 頂点 ${m}$ 辺のグラフを考えます。

Dinic法で解く場合、計算量は ${O(n^2m)}$ となりますが、様々な条件下でより計算量が落ちることがあります[11]。

他にも最大フローを求めるアルゴリズムとして

Ford-Fulkerson[12]： ${O(Fm)}$
Edmonds-Karp[13]： ${O(nm^2)}$
Push-Relabel[14]： ${O(n^3)}$ や ${O(n^2\sqrt{m})}$

などがあります。

ライブラリの作成

これまでの説明をもとに燃やす埋める問題を解くライブラリを作る場合、以下のような機能があればいいと思います。

ゴミの処理方法の数(必須)

各ゴミの処理方法の数 ${k_i}$ を与えます。何よりも先に必要です。

ゴミの処理方法による損失(必須)

各ゴミの処理方法による損失 ${cost_i(x),(1\leq x\leq k_i)}$ を与えるとその損失に応じた辺を張ります。負の数でも構いません。

ただし、損失が与えられた時点で辺を張るのではなく最小カットを求める直前に辺を張るようにしてください。後程説明する他の種類の損失で ${cost_i}$ の値が変更される場合があるためです。

${2}$ つのゴミの処理方法による損失(必須)

${2}$ つのゴミの処理方法の選択間にかかる損失 ${cost_{i,j}(x,y),(1\leq x\leq k_i,1\leq y\leq k_j)}$ を与えるとその損失に応じた辺を張ります。
[2つのゴミの処理方法による損失]で説明した非負の条件を満たすことを関数内で確認するようにしましょう。

損失が与えられた時点で辺を張ってもいいですが、後から変更される場合もあるので注意してください。

答えの復元

ここで説明したとおりに最小カットの復元を行いましょう。

頂点 ${i_{x}\in S}$ かつ ${i_{x+1}\in T}$ であるならば処理 ${x+1}$ を選んだことになります。

複数のゴミのうち ${1}$ つ以上が処理 ${1}$ をされたときの損失

たまにこの制約がある問題を見ます。

任意の ${i}$ で ${k_i=2}$ ならコレとコレで実現できます。
他にも「複数のゴミのうちすべて処理 ${1}$ をしたら ${C > 0}$ の利得」に言い換えることもできます。

${k_i > 2}$ の場合にも拡張できますが、変な制約になります(素直に「 ${1}$ つ以上が処理 ${x}$ をしたら ${C}$ の損失」みたいにはなりません)。

${3}$ つのゴミの処理方法における損失

[3つ以上の処理方法がある場合]で説明したものです。

数回だけこれが必要な問題を見ました。

その他の損失

損失問題2はどこかで見たような記憶がある程度。
[より複雑な損失]や損失問題3の損失は見たことないです。

流行り出したら作るくらいでいいでしょう。

練習問題

練習問題 ${1}$ 🔗
長さ ${N}$ の整数列 ${x=(x_1,x_2,\dots,x_N)}$ を作ろうとしています。各 ${i(1≤i≤N)}$ について， ${x_i}$ の値の候補が ${M}$ 種類あり、そのうち ${k}$ 種類目の値は ${A_{i,k}}$ です。なお、 ${A_{i,k}}$ を選ぶ場合には、 ${C_{i,k}}$ のコストがかかります。また、 ${x}$ を決めたあと、各 ${i,j (1\leq i < j\leq N)}$ について、 ${|x_i−x_j|×W_{i,j}}$ のコストが追加でかかります。最終的なコストの総和としてありうる最小値を求めてください。

解説

燃やす埋めるライブラリを作る動機になる問題です。

[3つ以上の処理方法がある場合]を実装すれば解けます。
各 ${i,j}$ 間に張られる辺の数は ${O(M)}$ であることも簡単に分かります。

練習問題 ${2}$ 🔗
${n×m}$ のマス目が与えられます。既に白か黒で塗られているマスがあり、その他のマスは塗られていません。色が塗られていないマスをすべて白か黒で塗り、マス目上のチェックパターンの数を最大にしたいです。 ${2×2}$ の正方形を形成する ${4}$ つのマスは、以下のいずれかのように塗られている場合、チェックパターンであると言います。

チェックパターンの数の最大値とそのときの塗り方を求めてください。

解説

各マスの選択肢は[白で塗る/黒で塗る]です。既に塗られたマスを異なる色で塗ろうとする選択には ${\infty}$ の損失が発生するようにします。

すべての ${2×2}$ の正方形に対して、チェックパターンなら ${1}$ の利得が発生するようにしたいですが、このままではうまくできません。

ここで、 ${i+j\equiv 0\bmod{2}}$ となるマス ${(i,j)}$ の選択肢を[黒で塗る/白で塗る]に変更すると、チェックパターンの制約が「 ${2×2}$ の正方形を形成する ${4}$ つのマスすべてが選択肢 ${1}$ /選択肢 ${2}$ を選ぶ」と言い換えられるのでコレやコレが使えます。