とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

Code Festival 2017 J (Tree MST) と 距離空間上のボロノイ図

春ですね。今回はCode Festival 2017のJ問題に対する面白い着眼点を紹介します。

問題はこちら -> J: Tree MST - CODE FESTIVAL 2017 Final | AtCoder 1900点!

ボロノイ図の説明はこちら -> ボロノイ図 - Wikipedia

想定読者層 :

  • MSTを知っている人
  • Kruskal法の適用中、頂点x,yを結ぶ辺が飛んで来たあと、それをMSTの辺として選んでも選ばなくてもその時点で構成中のMSTの辺のみを利用してxからyへ到達可能である、ということを理解している人

二次元空間上に点を配置した時の最小全域木(MST)のコスト

さて突然ですが、このサブタイトルの問題はどう解けるでしょうか。
やはり点の個数Nに対してO(N log N)程度で解けてほしい気持ちがありますが、
各点対間の距離を計算してしまうようではO(N^2)かかってしまいます。


いきなりですが、この問題の答えを言ってしまうと、

  1. ボロノイ図を構成する
  2. ボロノイ図で隣り合っている領域(点でなく、辺で隣り合う)に対して、それぞれに対応する頂点間の距離を計算する
  3. 計算した点対間のみの情報を利用してMSTを解くアルゴリズムに放り込む

です。

つまり、下図の例ですと、全部で6組の点対のうち、左側の点と右側の点を結ぶ点対は領域が接していないため計算する必要がないということです。
f:id:tokoharu-sakura:20180401021903p:plain


二次元ユークリッド空間上でボロノイ図を構成するO(N log N)のアルゴリズムが存在することが知られていて(参考 : Fortune's algorithm - Wikipedia)、さらに、(こういうアルゴリズムが存在するなら当然)隣接する領域の組の個数はO(N)であることが知られている(参考 : ボロノイ図とその3つの性質 | 高校数学の美しい物語 )ため、 このMST問題はO(N log N)で計算できることになります。

やはりポイントとなるのは「ボロノイ図で隣り合っているところしか見なくてよい」というところに尽きます。なぜこうなるのかをざっくり下図を用いてスケッチします。
f:id:tokoharu-sakura:20180331223807p:plain

これから、d(x,y)でx,y間の距離を表すことにします。

上図では、点x,y をおき、その中点をa、 さらに点zをd(x,a) = d(y,a) > d(a,z)となるようにとっています。
ボロノイ図で領域が隣接していない点対x,yをとった場合、このようなa,zがとれます(厳密にはとれない場合もありますが、それは細かいので考えないことにします)。

d(x,a) > d(a,z)の両辺にd(x,a)を加えれば、
d(x,y) = 2 d(x,a) > d(x,a) + d(a,z) >= d(x,z) がわかります。
これはd(x,y)と d(y,z)の関係に対しても言えます。

すると、Kruskal法では点対(x,y)より点対(x,z), (y,z)のほうが先に評価されることがわかります。
こうなると、点対(x,y)を比較するころには(x,z), (z,y)が先に連結になっていることから(x,y) の間もすでに連結だとわかるので、Kruskal法でこの点対(x,y)は必ず棄却されることになります。
したがって、点対(x,y)の距離の情報d(x,y)がなくてもアルゴリズムの返す解に影響はありません。

このような気持ちで、ボロノイ図を用いたアルゴリズムを構築することが可能です。

2次元空間からグラフの空間へ

次の問題を考えましょう。

距離付きのグラフG=(V,E,w)とVの部分集合Uを用意します。
集合Uに含まれる2点x,yの距離d(x,y)をグラフG上でx,yを結ぶ最短距離とします。
頂点集合としてUを持つ完全グラフH=(U,E',d)におけるMSTの最小コストはいくつか?
(つまり、xyを結ぶ辺のコストをd(x,y) とするときのMSTを求める問題です )

この問題は、距離を定義する空間を2次元のユークリッド空間から指定したグラフGから作られる空間にしたとみなせます(言い回しが数学的には雑ですが勘弁してください)。

では、この問題にも先ほど紹介したボロノイ図を用いた解法を用いることはできるでしょうか?

答えはYesです。上で用いたボロノイ図の説明をそのまま使う方針で説明可能で、その際「中点」など、ユークリッド空間特有の表現を距離空間上の言葉に直せば適用できます。

この説明で網羅していないのはスターグラフのようなケースで、要するにある頂点が多くの領域の境目になっているケースです。
そうなると、それぞれの境目について点対の距離を計算したいため、頂点数の二乗個の辺をアルゴリズムに突っ込みたくなります。
しかし、このケースでも、任意の点対が同じ距離なだけなので、Kruskal法を実行する際には順番を気にしなくてよいです。
したがって、代表点とその他の点を結ぶ辺のみをアルゴリズムに放り込めばよいことがわかります。

以上の考察から、次のアルゴリズムを得ることができます。
(ただ、言葉だけだとなんとなくわかりづらいので、この問題はボロノイ図っぽくやって境目を見つけれてMST、でOKだと思って飛ばして問題ありません。実際次節に図があるので、それだとイメージをしやすいかと思います。)

  1. プライオリティーキューに、Uに含まれる頂点と距離0の情報を挿入します。このキューの順序は距離で付けます。
  2. キューが空でない限り下のことをします
    1. キューから距離が一番小さい頂点vを選んで、キューからpopします。
    2. 頂点vに対して、まだ以下の説明にある隣接頂点を見ていく処理をしていないなら、その距離とU上のどの頂点から来たかを記録し、以下のように隣接頂点を見ます。
    3. 隣接頂点uを見て、これがすでに記録されているなら、頂点uに登録されている頂点と頂点vに登録している頂点の距離を、(uに記録された距離) + (vに記録された距離) + 辺v,uの距離として、Kruskal法で使うコスト情報として登録します。
    4. 隣接頂点uが記録されていないなら、これをプライオリティーキューに挿入します。このとき、vに記録した距離に(v,u)の距離を足したものであること、Uのうちどの頂点から来たかを伝えます。
  3. Kruskal法を動かす

このアルゴリズムはグラフGの頂点数Nと辺数Mに対して、だいたいO( ( N+M) log (N+M))程度で動作し、Kruskal法のために登録する辺数もM程度で抑えられるので、頂点集合Uのサイズが膨大でも動作します。

Code Festival J, Tree MST

本題に戻ります。しかし、ここまでの説明を読めば、この問題はかなり簡単ではないでしょうか。
というのも、TreeMSTで定義されている距離をグラフを用いて書いてみると以下のようになります。(この図は本家問題文の例1に対応しています)

前節の説明で頂点集合Uに相当するのが、1,2,3,4と黒字で番号がついている頂点の集合で、Vは1',2',3',4'を加えた8頂点からなる集合になります。
f:id:tokoharu-sakura:20180401000115p:plain

このようなグラフの作り方で、「頂点 u から頂点 v までの距離」と「Xu+Xv」の和、という距離をグラフで自然に表現できます。

これにボロノイ図的な考え方を適用すると次の色分けができます。
f:id:tokoharu-sakura:20180401002901p:plain

これで全域木に登録される辺の候補は、領域の境目となっている(1,2), (1,3), (1,4) でよいことがわかるので、コストは(1+1+3) + (1+1+2+5) + (1+1+2+3+1) = 22になることがわかります。

このように、ちょっとオーバーキル気味ですが、ボロノイ図的な方針で解くことができます。
コードは Submission #1818510 - CODE FESTIVAL 2017 Final | AtCoder ここにあります。短いですね。(なお、とくにこの問題では領域の境目の個数がちょうどN-1個になりますので、Kruskal法を使う必要はありません。)

また、この着眼点から考えると、TreeMSTの元となるグラフを木でなく、一般のグラフに拡張しても自然に解けることがわかる点も面白いです。

類題

snukeさん紹介の問題

自然にこれも解けますね(Judgeがどこにあるかわかりませんが)。

JOI 春合宿 2014 Day2 水筒

(HIRさんに教えていただきました。ありがとうございます!)
目標は違いますが、アイデアはよく似ています。
JOI 2013/2014 春季トレーニング合宿 課題

この方針が適用できない問題

今回紹介したボロノイ図的な考え方は、ある距離行列が与えられたとき、これを適切なグラフに埋め込んで表現できる場合に適用可能です。
したがって、次のような問題には適していないと思います。https://csacademy.com/contest/round-72/task/rectangle-mst/

この場合はこの距離行列を特定のグラフに埋め込むことができそうにありません.....

まとめ・感想

変なMSTが解けるテクとしてそこそこの汎用性がある気がします。

それにしても、計算幾何のアイデアをグラフに持ってきて解けるというところが非常に面白いです。ほかの計算幾何のアイデアもグラフに持ってこれないか、といった方向で問題を考案することもできるかもしれません。

Project Selection (燃やす埋める) 周りの話についてもう少し考えた

Competitive Programming Advent Calendar 2017 - Adventar アドベントカレンダー最終日です。


先月はこの過激記事をご覧になった方も多いのではないでしょうか。 : 『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ

これについてもう少し色々な視点から整理したり、最近考えていた拡張を書いていきます。調査が不十分な点・誤植もあるかと思いますが、ご容赦ください。(誤植は教えていただけると助かります)
以下、Project Selection Problemは略してPSPとしておきます

また、前回の記事周りの話はそんなに面白くないので後回しにします。

拡張を考えていた話

モチベーション

私はPSPの信者なので、できるだけこれをサブルーチンとして利用することで、いい感じに問題を解きたいです。
しかし、イマイチ使い方がわからない問題があります。それが https://www.codechef.com/DEC14/problems/RIN この問題です。
想定解法では、面白いグラフの張り方をしています。知らない方はこの問題のeditorialをご覧ください。

ただ、今後紹介する方針ではなく、editorialにあるグラフの方が綺麗だと思います。

拡張

この問題をなんとかPSPの枠組みで解けるようにするために、PSPに対して次のような拡張をします。

プロジェクト i は集合 0,..., K-1 のうちのどれかの値が割り振られるとします。
このとき、p[i,0], ..., p[i, K-1] だけの利得がそれぞれ得られます。簡単のため、p[i, 0]=0とします。

また、プロジェクト i に k 以上の値を割り振れば プロジェクト j に t 以上の値を割り振らないと コストcが発生します。
プロジェクトに値を割り振ることで利得を最大化せよ。

これは一つのプロジェクトあたり、次のような利得と関係をつけたグラフをつけると表現できます。
矢印はINFコストを表現します。
f:id:tokoharu-sakura:20171224205019p:plain

一番左が選ばれるとその右がすべて選ばれるため、合計の利得はp[K-1]とみなせます。一番左を選ばず、その右が選ばれると合計利得はp[K-2]になります。どれも選ばなければ0( = p[0])です。このようなグラフを用意することで上記の拡張でも表現できることがわかります。

では、上記RINを解くときにはどうなるのか。必要なものは講義xの後に講義yを取る条件を入れ込むことです。
これは「講義xがk以上なら、講義yはk+1以上である。」という条件を各semester kに入れれば表現できます。

つまり、次のようなグラフを作るのがざっくりした方針になります。
f:id:tokoharu-sakura:20171224211542p:plain

細かいことを言うと、開講されていないsemester などを考慮する必要があるので、そういう頂点は利得を -M(Mは十分大きい定数)とする
などの工夫が必要と思います。その点で、想定解法より汚くなるかもしれません。

ただ、想定解法とは異なるグラフが構成できることは非常に興味深いです。

さらなる解釈

このような一般化PSPは次のことをしているとも思えます。

A[K-1] ⊂A[K-2]⊂ ... ⊂ A[0] であるときに、点x を 集合A[0]内に配置する。
点x をおいた場所が x ∈ A[i] ならq[i]点を獲得する

また、x が A[i]内にあるとき、 y はA[j] 内にいなければ c 点減点される。

これを見ると、集合の切り分け方が部分集合関係の鎖になっていることが本質的な気がしてきます。
そこで、次の問題を考えてみましょう。

3状態へ割り振るタイプの問題


いくつか前の記事でも登場しましたが、この問題で前節で紹介した切り分けが重要であることを確認します。

この問題が初見であれば、次のように、「燃やす集合」、「埋める集合」といった集合をそれぞれ作るアプローチを取るところから始めるのではないでしょうか。
f:id:tokoharu-sakura:20171224215219p:plain
実際こういった気持ちでスタートしてもPSPを構成できます(参考 : 続:『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ)が、片側の状態の01を反転する必要が出るため、なんだか奇妙でした。

しかし、先述した部分集合の鎖で考えることが自然だと思うと、次のように層を分けるのが自然そうに見えます。
f:id:tokoharu-sakura:20171224215503p:plain
つまり、(燃やす) ⊂ (埋めない) ⊂(全体)の関係です。
入れたい条件は、「xを燃やすならyを埋めない」の関係だったので、制約もちゃんと入れることができることがわかります。

TCO2017 Semifinal2 500 RatingProgressAward

これも何件か前の記事で紹介しました。(詳細は TCO2017 Semifinal2 500 RatingProgressAward - とこはるのまとめ

この記事を参照すると、問題の言いかえは次のようなものでした。

ProjectをN個用意し、それぞれのProjectは proj[i]=0,1,2のように3値をとれるものとします。
このとき、a[i]からb[i]に到達可能ならproj[a[i]] >= proj[b[i]]を満たさなければならないとき、
proj[k]==1となるProject kに関して、change[k]の総和を最大化せよ。

この問題での集合の切り分けはproj[k] >= 2, proj[k] >= 1 とわけることが自然でしょう。

まず、「proj[k]==1となるProject kに関して、change[k]の総和」は
proj[i] >= 1ならchange[i]を足し、proj[i] >= 2ならchange[i]を引けばOK。

次に「a[i]からb[i]に到達可能ならproj[a[i]] >= proj[b[i]]」は
proj[b[i]] >= 1 ならば proj[a[i]]>=1,
proj[b[i]] >= 2ならば proj[a[i]] >= 2の制約を入れればOKです。

これだけわかれば解けてしまいます。
これでかなりお手軽に解けるようになったのではないでしょうか?

前記事の感想などを見て

色々思ったことを書きます。

前記事においてPSPの有用性を主張していました。
意図としては、

  • より思考をショートカットできるしお手軽な道具じゃないか?
  • ちゃんとこの辺りのテクにはそういう名前がついている

の周辺の2点を主張していたつもりでした。
これについて共感してくれる人が少なかったのはかなりショックでした。

ただ、この二点については考え始めるとどっちでもいいのかもという気持ちになってきました。

後者の名前は、twitterや会話における意思疎通において、解法のスケッチを伝える上で「燃やす埋める」は大変便利です。だからこれからも残り続けるでしょう。
ただ、PSP側も何か調べものをする意味で覚えておいて損はないとは思っています(マージテク <-> weighted union heuristics の関係に似ていると考えています)

前者のテクそのものとしての有用性は個人的には

  • 適当にグラフを作ると後からグラフを変形する可能性があるという点
  • 最大流の結果との定数を足し引きする整合性を管理するのが面倒

という二点が気がかりでした。
両方の懸念も、考え方に慣れればどうでもよさそうです。
個人的には最初はPSPの手順そのままに考えればミスも減るし入門として適していると考えてはいますが。

そもそも論として、強い言葉を使いすぎたのはまずかったです。

それから、skyさんのこのツイートにはかなり救われました。この場で感謝いたします。

最後に

この辺りの最大流のグラフの作り方は必ずしも一通りではないケースが多いと認識しています。綺麗なグラフで解けている場合もあれば、意味不明なグラフで解いているケースもあり、解答者が何を考えているのかわからないこともあります。
いろんな人がこの問題に興味を持てば色々な解釈がわかって面白くなる気がしています。実際、次の記事は私の一連の記事のあとに公開されました。最後の例が面白いです。
最小カットとProject Selection Problemのまとめ · うさぎ小屋

ところで、これは今回の話と無関係ですが、私は競技プログラミングに対して真っ当な努力はできていないので、今年のAdvent Calendarの記事も大変助かっています。今年も雰囲気でしか知らなかったテクをちゃんと知ることができて大変有益でした。多分世の中ガチ勢ばかりではなく、私みたいな人はたくさんいると思うので、来年のAdvent Calendarでも記事を書いてほしいです!

みなさんよいお年を!

第2回ドワンゴからの挑戦状「花火」に対するシンプルな解法と最小費用流の双対

競技プログラミングアドベントカレンダー2017(その1)の二日目の記事です。
adventar.org


この記事では花火に対するシンプルな解法を説明します。これは最小費用流の双対問題を用いて説明できますので、そういったことに触れつつ解説します。本文は次のPDFに書きました。 http://tokoharu.github.io/tokoharupage/docs/advent2017.pdf

面白いポイントとしては、このテクを用いれば UTPC2012の"じょうしょうツリー"もかなりシンプルに書ける点だと思います。じょうしょうツリーについてはその解説では meldable heap を用いるというのが想定解法でしたが、今回紹介する方針でやればかなりシンプルにかけるかと思います。

そのほか

  • tikz を使ったけどハマったときに結構苦労するなぁ
  • Project Selection Problemの件はちょっと待ってください。

TCO2017 Semifinal2 500 RatingProgressAward

(UPD 12/24) 説明に誤りがあったので修正。

前回の続きです。

前回はいろはちゃんの疑問に答えたつもりでしたが、聞いてみたところ違った問題のことを指していて、表題の問題だったようです。
link :TopCoder Statistics - Problem Statement
今回もProjectSelectionProblemを経由して解いていきたいと思います。

問題概要

  • 授業をN課程とります。
  • 順番は任意でよいですが、1課程ずつ順番に受講しなければなりません。
  • 課程b[i]を受講するためには、すでに課程a[i]を修了している必要があります。
  • 最初のレーティングは1200です。
  • 課程iを受けるとratingが += change[i]だけ変動します。
  • k個の課程受けた直後のratingをv[k]とします。k=0なら初期値です。
  • このとき、Rating Progress を max( { v[i] - v[j] | i > j } )と定めます。
  • 受講する課程の順番をうまく選ぶことでRating Progressのありうる最大値を求めよ。

解法

問題の言いかえ

この問題はある種のProjectSelectionProblemっぽくみえます。「ぽい」と表現した理由は、次のような問題に言い換えてProjectを定めることはできるものの、ProjectSelectionProblemのフレームワークに適用できない形だからです。

ProjectをN個用意し、それぞれのProjectは proj[i]=0,1,2のように3値をとれるものとします。
このとき、a[i]からb[i]に到達可能ならproj[a[i]] >= proj[b[i]]を満たさなければならないとき、
proj[k]==1となるProject kに関して、change[k]の総和を最大化せよ。

これをどうにかProjectSelectionProblemに適用しようと思っても、「ならば」の制約がうまく入らないためどうにもうまくいかなさそうです。この「ならば」がうまくいかないのは1,2の間の「ならば」と0,1の間の「ならば」が共存できないことに由来しそうなので、この二つの制約を分離することをこれから考えていきます。

Projectの定義

その結果、次のような2N個のProjectを作ってみることにします。

最初のN個 :

  • B(ベース)に属する <=> 0に属する
  • Aに属する <=> 1,2に属する

残りのN個 :

  • B(ベース)に属する <=> 0,1に属する
  • Aに属する <=> 2に属する

ただし、それぞれの種類のProjectで、最初からi番目が課程iに対応するものとします。

最後に得たい答えの求め方

このとき、どうすれば1に属する利得を計算できるかですが、最初のN個でAに属するProjectと、残りのN個でBに属するProjectのchangeの総和を足し、最後にchange[i]の総和で引けばよいです。(ちょっとトリッキーですね)

制約

次に制約を考えます。考える制約は二種類です。

  • 課程の順序制約

これはb[i]がAに属すればa[i]がAに属す制約でよさそうです。だからフロー用グラフにb[i]からa[i]に∞容量の辺を張ります。この制約はどちらの種類でも共通です。

  • 2つのプロジェクトの整合性制約

本来1つのProjectと扱いたいものを2つのProjectに分離しました。ここの整合性がとれていなければいけません。具体的には、前者でBに属し、後者でAに属している場合に0かつ2に属して矛盾となるためこれを避けたいです。したがって、後者のプロジェクトがAに属している場合に前者のプロジェクトはAに属している必要があります。だから N + i からiに∞容量の辺を張るような感じになります。

利得

次にProjectSelectionProblemの構成要素として利得があるのでこれを考えます。

これはBに属しているときから見た、Aに属したときの相対的利得になります。
最初のN個はBにいるときにchangeをカウントせず、Aにいるときにchangeをカウントしたいです。だから最初のN個の利得pはchangeそのままです。
一方、後のN個はBにいるときにchangeをカウントし、Aにいるときにchangeをカウントしません。だから後のN個の利得pは正負が反転して-changeになります。

ここまでで最大流のグラフを作り終えることができました。

最大流を除いた部分の整理

最後に、最大流の外側で計算する部分について整理します。

  • ProjectSelectionProblem内部での総和部分

これは利得のうち、正であるものの総和なので、 abs(change[i])の総和になります。

  • ProjectSelectionProblemのBに所属させる際に発生する利得。

これは後者のProjectで発生します。これはchange[i]の総和です。

  • ProjectSelectionProblem外部でもともと解きたい問題の答えを得る。

これは以前説明した通り、change[i]の総和を引きます。

これら3つを合計することで、 abs(change[i])の総和を事前計算しておけばよく、結局 sum(abs(change[i])) - maxflow(s,t) が答えになります。

コード

以上のまとめとして、ACしたコードの一部を載せます。max_flowのライブラリを持っていると仮定し、add_edge(v,u,c)はフローを流したいグラフに対してvからuへ容量cの辺を張ることを指します。

int RatingProgressAward::maximalProgress
(vector <int> change, vector <int> a, vector <int> b) {
  int N = change.size();
  int ans = 0;
  int s = 2 * N, t = s + 1;
  for(int i=0; i<N; i++) {
    ans += abs(change[i]);
    add_edge(i+N, i, INF);
    if(change[i] > 0) {
      add_edge(s, i, change[i]);
      add_edge(N+i, t, change[i]);
    }
    else {
      add_edge(s, N+i, -change[i]);
      add_edge(i, t, -change[i]);
    }
  }
  int M = a.size();
  for(int i=0; i<M; i++) {
    add_edge(b[i], a[i], INF);
    add_edge(N + b[i], N + a[i], INF);
  }
  int ret = max_flow (s,t);
  return ans - ret;
}

個人的には割ときれいなグラフだと思っています。

本番でACされたコードを貼っておきます(要Login)。
tourist https://community.topcoder.com/stat?c=problem_solution&rm=330662&rd=17017&pm=14719&cr=22263204
ikatanic https://community.topcoder.com/stat?c=problem_solution&rm=330662&rd=17017&pm=14719&cr=22711754

全く違いますね。ちゃんと読めていないのでわからないですが、もっと簡単な考え方もあるのかもしれません。何かご存知の方がいらっしゃれば教えていただけると幸いです。

コメント

こうして出されてみると難問でしたが、考察の流れを考えれば拡張が容易にできそうにも見えます。
というのも、今回は 2 > 1 > 0にわけた領域のうち、それぞれの利得の重みを0,1,0としたような問題でしたが、これはp,q,rみたく係数をつけて一般化できそうに見えます(本当にできるか未チェック)。
こういう想像が働くようないい感じの解が得られて割と満足です。

続:『燃やす埋める』と『ProjectSelectionProblem』

http://tokoharuland.hateblo.jp/entry/2017/11/12/234636の続きです。
煽り気味な記事を書いたのは反省中です。気を悪くされた方がいましたら申し訳ありません。
こういうのは無駄に人の心を煽っても仕方なくて、ACできたら正義なのでどちらを選んでも問題はない、と考えた方がよかったかと思います。
また、前回の記事で抜けていた点として燃やす埋めるは最小化問題で、ProjectSelectionProblemは最大化というところも大きな違いでした。これは先ほど少しだけ追記しました。

ところで、今日は続きの話題を書きます。

いろはちゃんから上のような疑問をいただきました。

答えはできます、が、従来と比べて思考量が減るかは判断できないのでどっちでもいい気がします、というところです。

3つに分けるタイプの問題?

いろはちゃんの問題ですが、要するに次の問題だと認識しています。

これの解法ですが、まず2N個のProjectを用意します。
次にはじめのN個には次の意味を持たせます
B(ベース)にいる <=> iは何もしない
Aにいる <=> iを燃やす

残りのN個には次の意味を持たせます
B(ベース)にいる <=> i を埋める
Aにいる <=> iは何もしない

このとき、禁止制約は 『iを燃やすかつiを埋める』、と、『iを燃やすかつjを埋める』という形の制約になります。
この条件は結局『iを燃やすならばjは何もしない』とすれば回避でき、これはProjectの世界で『iをAにおけば、(j+N)はAに置かないといけない = 罰金INF』ということなので、めでたくProjectSelectionで書けました。

総コストについてですが、まず最初B(ベース)にいることを考えるため、埋める利得の総和を事前に足しておきます。
次に、ProjectSelectionProblemの答えにおける総和部分はBから見てAのスコアが相対的によいプロジェクトでのスコアの総和なので、これは結局燃やす利得の総和です。
最後に、ProjectSelectionProblemの答えにおけるmaxflowの値を引けば、これがもともと知りたかった3つに分けるタイプの問題の答えになります。

結局反転は登場せざるを得ないし、3択を2択にするのがトリッキーなので、そこのややこしさは回避できないでしょう。また、できるグラフは従来の考え方と大差ないはずです。
ただ、もともと最大化問題のフレームワークなので、minとmaxがごっちゃになるリスクは減るんじゃないかとは思います。

そう考えると、最小化問題だと燃やす埋めるで考える方がやりやすいのか、気になります。意見などありましたらお寄せください。

今日のまとめ

前回の記事のごめんなさい
3つに分ける問題も扱えます

『燃やす埋める』と『ProjectSelectionProblem』

(UPD 11/15)
下の記事を書くにあたってやらかしたこととか、
返ってきた辛辣な反応を見て、いろいろ言いたくなったんですが、
自分の過ちがどんどん浮き彫りになった気がします。それはまた今度書きます。

個人的にPSP経由の解法はカットが苦手な人にはオススメだと思うので、
そういう人はぜひ試してほしいです。
次記事とか次々記事あたりは面白いんじゃないでしょうか。

      • -

こういうツイートをした。

『昨日の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のフレームワークに自然に落ちる上、できるグラフに負辺が登場しません。何も考えてないのにこういうハマり方を回避できるのは地味にお得だと思いませんか?

まとめ

燃やす埋めるには緩やかに滅んでほしいと思います

AGC 016 C (+/- Rectangle) と Farkas' lemma

AGC 016 Cを考えていると気づいたことがあるので、紹介します。

まず、AGCの問題文 : C: +/- Rectangle - AtCoder Grand Contest 016 | AtCoder
この問題は要するに、局所的には負にしつつ、全体は正にする、というような気分のような問題です。
私も結局よくわからず、最後は答えを見てなるほど~~、と言っていました。

では次にFarkas' lemmaを見てみます。
Farkas' lemma - Wikipedia
これはリンクにある問題2つのうち、必ずどちらか一方のみに解がある、というなかなか面白い補題です。

この式の2番の方に着目してみましょう。{y=-y'}として{y'}で式を立てれば不等号の向きが入れ替わります。

さてこの式、AGCの方の問題とほぼ同じではないですか?

{b}を要素がすべて1のベクトルすれば{b^T y' > 0} は正にする制約だし、
{A}側も、適切に設定すれば局所的に負にする制約にできます。

じゃぁこのとき、1式はどうなるのか。これは各小長方形1つに変数が1つ対応して、これが{x}になります。
{b}はマス1個に対応して、どの要素も1。{Ax}は小長方形の重み{x}をそれが含む各マスに足しこむ操作とみなせます。

ここまでわかれば、1式が解をもつかどうかはすぐにわかり、{H}{h}の倍数かつ{W}{w}の倍数であることが必要十分になります。
すると、2式が解を持たないための条件はこの条件だとわかるのです。

ということで、解が存在する・しないの判定は、このようなアプローチで見つかることがわかりました。(やったね!)

AGCの問題を解こうと思うと、ここからさらに構成する必要があるのですが、
このアプローチだけだと少し厳しそうに見えます。
というのも、Farkas' lemmaのアプローチで解{y'}を構成しようと思うと、
分離超平面を構成する必要があります。
これを今回の大きさの行列に適用するのはしんどいので、特別な性質があればよいのですが、
ぱっとはわかりませんでした。

誰かわかる人がいれば教えてください。