グリッドを白く塗る問題。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

これ解けないんですが、どうやるんだろう。（というかNP困難に帰着された） ちなみに最大回数なら解けました。 twitter.com/drken1215/stat…

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

行と列をそれぞれ頂点とした二部グラフを考えて、黒マスに対応する場所に辺を貼ったグラフを考える。 操作で選ぶ黒マスの集合はマッチングになる。（端点を共有する二辺は共には選べないため） で、全部が白マス＝極大マッチング。 なので、最小極大マッチングに帰着された。 ja.wikipedia.org/wiki/%E6%9C%80…

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

サンプル： 黒白白 黒白白 白黒黒 →2 黒白白 黒白白 黒黒黒 →1

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

最小極大マッチング、最大次数が3の二部グラフですらNP-Hardらしい。（あと最大次数が3の平面グラフも） semanticscholar.org/paper/Minimum-…

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

「辺をいくつか選んで、どの辺も選ばれた辺のどれかと端点を共有するようにするときの、選ぶ最小個数」みたいな問題（つまり選ぶ辺が端点を共有しても良い）も、最小極大マッチングと同値だな。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

最適解で辺u-vと辺u-wを選んだとすると、頂点xを端点とする辺を１つも選んでないような辺w-xが存在するはず。（じゃなければu-wを選ばなくて良いため） ならば、u-wの代わりにw-xを選んでも最適解となる。 これを繰り返せば選んだ辺が端点を共有しないような最適解が見つかる。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@drken1215 @toku51n 白マスも選べる、とするとそれっぽくなりますが、それでも結構難しい気がします（NPまでありそう） 最小辺被覆の撃墜例： 黒黒白白白 白白黒白白 白白黒白白 白白白黒白 白白白黒白 白白白白黒 白白白白黒 →3

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

昨日の問題、(連続)緩和問題なら多分解けた。 【問題】 H*Wのマス目のいくつかのマスに人がいる。 各マスには電球があり、パワーをx(実数)にすると、同じ行/列のマスの明るさがx、電球があるマスの明るさが2x増える。 人のいるマスの明るさを全て1以上にするとき、パワーの合計の最小値を求めよ。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

制約は1≦H,W≦500とか。復元もつけようかな。 サンプル： H,W=4,2 人無 人無 無人 無人 → 1.3333…(4/3) 構成： 1/3,1/3 0,2/3 0,0 0,0 （電球のあるマスは２倍明るくなることに注意） ちなみに各マスに明るさはこうなる 1,5/3 1,5/3 1/3,1 1/3,1

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解法(下準備): まず言い換えをすると、 ・行と列にそれぞれ実数を割り当て、人がいるマスの行/列の値の和が1以上になるようにしたい ・行の値の和と列の値の和が等しくなるようにしたい (値の割り当てから解の復元は、適当に左上から貪欲に取っていけばできる)

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解法(前提): まず、行の和と列の和が同じじゃなくていいなら、図のようなグラフでmincutを求めれば良い。 （S→行に1の辺、人がいるマスに対応する行→列にINFの辺、列→Tに1の辺） pic.twitter.com/P0j826h1lY

拡大

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解法(本編): mincutのLPに行と列の和が同じっていう制約を入れる。 制約式は tokoharu.github.io/tokoharupage/d… の5pにある式でいうと、(Σe∈(S→Ri){y_e})-(Σe∈(Ci→T){y_e})=0みたいな感じ。 これはラグランジュ緩和で解ける (参考: slideshare.net/wata_orz/ss-91… ) 上の式の左辺をg(y)としておく。（つづく）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解法(本編2): max(λ){min(y){Σc_e*y_e - λg(y)}} が答えになる。 内側を式変形すると、S→Rの辺の流量を-λ、C→Tの辺の流量を+λした問題になる。 解を求めるのは、λを三分探索しても良いし、内側の最適解でのg(y)の正負が入れ替わる場所のλを二分探索しても良い。 この問題だとλは-1~1の範囲で良い。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解法(復元): 最適解でg(y)=0になるλがあれば簡単ですが、あるとは限らないので工夫が必要。 g(y)≦0のうちの最大とg(y)≧0のうちの最小の解をちょうど良い比率で混ぜてg(y)=0にする。 全ての整数解を平面の(行の和,列の和)の位置にプロットして、凸包とって、直線y=xとの交点を構成するイメージ。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解法(実演): サンプルだとλ=-1/3のときmin(y){~}が4/3になってmaxになる。 整数解(0,2)と(2,1)を混ぜて、(0,2)*1/3+(2,1)*2/3=(4/3,4/3)にする。 行={0,0,0,0},列={1,1}と 行={1,1,0,0},列={0,1}を混ぜて 行={2/3,2/3,0,0},列={1/3,1}にして、復元すると出力例になる。