-
masashinakata
- 1294
- 0
- 0
- 0
-
- いいね！0
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
具体的には、次数が全部kの二部グラフの左からx頂点取ってきて、それに繋がってる右の頂点がy頂点だったとする。それらの間の辺はxk本あり、次数がk以下であることを考えるとx≦yなはずってなるのでHallの定理できる。
2020-04-05 12:00:07
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
正則にする魔法： 最大次数をkとする。 1. 次数k/2以下の頂点が複数あればマージする 2. 適当に頂点を追加して左右の頂点数を合わせる 3. 残りは適当に辺を追加して次数を合わせる（多重辺もokなら本当に適当で良さそう） このとき、辺の本数は高々2倍+kにしかならないので嬉しい。
2020-04-05 12:12:40
maspy
@maspy_stars
@snuke_ 2の魔法が気になりますね。 これができると、再帰的にやらなくても、1つ完全マッチング引いたあと魔法を使うで解けてしまいそう？
2020-04-05 12:16:18
koyumeishi
@koyumeishi_
GCJ qual D の丁度 150 回クエリ出力しないといけないか問題は配布されてるテスター見たら打ち切っても大丈夫になってたからそこで判断した
2020-04-05 12:26:54
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
@maspy_stars 2の魔法よく分からんですね。正則二部グラフの完全マッチングを調べてもO(n log n)しか見つけられなくて、それだとlog二乗になりそう・・・？（と思ったけどn頂点k次ならO(n log n log k)でm=nk>=n log kだからO(m log m)ではあるのか・・・？謎）
2020-04-05 12:26:58
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
@maspy_stars いや、括弧内の計算量嘘ついてました（さらに謎が深まった） あと、再帰的にやらなくて〜がよく分からないんですが、毎回マッチング求めてると容易に二乗っぽい感じになりませんか？
2020-04-05 12:30:53
tsutaj
@tsutaj
D: i と N-1-i で値が同じところ・異なるところを見つけるとどういう操作が行われたかが求められる (一方しかない場合は flip したかどうかを考えるだけ) E: 対角線に、ある要素がちょうど N-1 個存在すると不可能で、それ以外だと可能なので、そのような数列を見つけた後は完全マッチングっぽいフロー
2020-04-05 12:33:24
maspy
@maspy_stars
@snuke_ 次数が奇数のときの彩色を手に入れる魔法の存在を仮定して、 次数が奇数なら魔法、次数が偶数なら、完全マッチングを見つけることを1回だけやったあと魔法。 の意図です。
2020-04-05 12:33:30
tsutaj
@tsutaj
GCJ の E に似た雰囲気の問題、前に AGC で出てなかったっけ これに似ている気がした atcoder.jp/contests/agc03…
2020-04-05 12:37:01
Yak!
@yak_ex
#GCJ #Codejam 問題E ググって出てきたラテン格子をランダム生成するJacobson and Matthews' algorithmベースにこねくり回しましたがHiddenはTLEで駄目でした。40x40なら通って良さそうくらいにはなったんですが。
2020-04-05 12:42:37
Yak!
@yak_ex
ラテン格子を調べるなかで見つけた記事。 en.wikipedia.org/wiki/Futoshiki Futoshikiというパズル自体を知らなかったのだが"Not to be confused with Futanari"はちょっとインパクトあると思う。
2020-04-05 12:57:32
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
k-正則二部グラフの完全マッチングO(m log n)： ipsj.ixsq.nii.ac.jp/ej/?action=rep… まずk=2^tだとすると、オイラー路を取って奇数番目の辺だけを残すっていうのを繰り返せばO(m)で完全マッチングが見つかる（Gabowのアルゴリズム）
2020-04-05 13:17:46
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
2^t-1<k<2^tの場合は、適当なダミー辺を追加して2^t正則にする。ここでダミー辺の割合は高々半分。 これに対してGabowをする（ただし奇数番目と偶数番目でダミー辺が多い方を捨てる） するとダミー辺がn/2以下の完全マッチングが見つかる。
2020-04-05 13:20:23
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
元のグラフにこのマッチングを2^t-k個追加すると、今度はダミー辺が高々1/4になる。 これに対してGabowをするとダミー辺がn/4以下の完全マッチングが見つかって・・・というのをO(log n)回繰り返せばダミー辺が0の完全マッチングが見つかる。
2020-04-05 13:22:33
maspy
@maspy_stars
この時点でスーパーおもしろいですね！！ （二部は要らなくて正則性をうまく使っている？） これで出来る理由が分かるのに5分かかったけど、任意の頂点の次数を半分にした部分正則グラフをとることを繰り返すとマッチングですか。 twitter.com/snuke_/status/…
2020-04-05 13:29:41
ꑄ꒖ꐇꌅꏂ🐾
@snuke_
天才すぎんか？ （ちなみにまだ読んでないけどO(m+n log n log k)もできるらしい） O(m log n)のを使えば元の辺彩色は多分O(m log m log k)。
2020-04-05 13:30:38