こういうツイートをした。
『昨日のARCに関してなんですが、個人的には、『燃やす埋める』という概念はそろそろ消え去るべきだと思っています。なぜかというとProjectSelectionの形そのものを覚えれば瞬殺だからです。だからみんな http://tokoharu.github.io/tokoharupage/docs/formularization.pdf のp7とかwikipediaのページを読んでほしい』
珍しく腹が立ってしまったから煽りっぽい感じで言ったので、少し落ち着き目でこれに対する色々を書いておきます。
そもそもこれらは何なのか。
結局のところ、最小カットに帰着して最大流のグラフに変換する際に楽をするツールというイメージです。
ProjectSelectionProblem
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem
次の問題が与えられます。
N 個の要素がある。最初どの頂点も集合 B に属しているが、これを集合 A に移すことで利益を最大化したい。要素 i が A に属する時には利得 p_i を得るという情報が与えられる。さらに 3 つ組の列 (xj, yj, zj) が与えられ、これは xj が A に属し、かつ yj が B に属していた時に zj(≥ 0) だけ損失をすることを意味する。得られる利得の最大値を答えよ。
この問題に対する解は (∑(v∈V) max(0, pv) ) − maxflow(s, t)で求めることができる。ただし、 maxflow(s, t) とは、
- 1. 要素に対応する点の他に，新しく s, t の頂点を導入した N + 2 頂点のグラフの上に、
- 2. pv > 0 であれば s から v に容量 pv の辺を張り、
- 3. pv < 0 であれば v から t に容量 −pv の辺を張り、
- 4. xj から yj に容量 zj の辺を張ったときの、
- 5. s-t 間の最大流の値
である。
違いは？
これら二つのテクから構築されるグラフはほとんど同じようなものです（実際、「ならば」の制約を言い換える操作は同じことをしています）。
違いは集合の扱いで、ProjectSelectionProblem では「集合Aに入った方が集合Bに入れるよりどれくらいお得か？」という量を持ちます。
一方で、『燃やす埋める』というテクでは集合Aに入るときのコストと集合Bに入るコストを両方持ちます。
『燃やす埋める』という概念に消え去ってほしい理由
燃やす埋めるタイプそのままが出てきたときに何も考えずに変換テクを使えるのは強いです。そういう意味でこの概念は消える必要は無いし、しばらく残り続ける言葉だと思います。
しかし、私はProjectSelectionProblemの方にメジャーにはなってほしいと感じます。端的に言ってそちらの方が洗練されていると思うからです。
- 相対的なコストで考えるほうが考えやすい
Aに属したときのコスト、Bに属したときのコスト、と分けるのは個人的にとてもややこしいと感じます。燃やす埋めるの直接適用が可能であればよいですが、たいていの場合、ベースケースに所属させておいて、そこから見たときの相対利得を考察する方がずっと楽だと思います。
- ローカルネームすぎる
この界隈、ローカルネームが流行ることが多いです。たいていの場合はその周辺にちゃんとした名前が無いからつけられているという認識ですが、今回はProjectSelectionProblemがすぐ近くにいるのに名付けられているので、なんだかなぁと思います。
- 変なハマり方をしにくい
例えば、ARC85で出た問題ではこういうハマり方をしている方がいました。
この問題はProjectSelectionProblemのフレームワークに自然に落ちる上、できるグラフに負辺が登場しません。何も考えてないのにこういうハマり方を回避できるのは地味にお得だと思いませんか？
まとめ
燃やす埋めるには緩やかに滅んでほしいと思います
追伸
2017/Practice/模擬地区予選/案内 - ACM-ICPC Japanese Alumni Group]
来週の模擬地区、私が準備している問題も出題されるからみんな参加してね！