TCO17 Algorithm Round 2C

agw @masashinakata

あと5時間。はて…?

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

解いた。228.64+344.31だったけどeasyがびっくりするようなミスで落ちた。落ちてなくてもparallelだと微妙な順位だったし結果オーライ。一応通過はできる点だったらしい。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Easyで、i=n-1を省こうとして「i<n」って書いててびっくりした頭大丈夫ですか・・・ MedのDemon判定ちょっと怖かった。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

EasyもMedもわりと面白かった。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Easy：隣接をswapすると累積和配列は高々１箇所しか変化しないため、scoreも高々１しか変わらない。昇順が最弱で降順が最強で、その間にKがあるならば、バブルソートしながら毎回scoreをチェックしていけばどこかでKになる。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Med：Angelが先に選んでDemonが後で選ぶとしてもAngelが勝てるならAngelだし、逆も同様。Angel判定は、s辺追加することでmincutをt+1以上にできるかで、0→n-1にt+1流すMCF（辺のコストはY=0,N=1）。

nico_shindannin（診断人） @nico_shindannin

そういや放送のEasyで、隣とswapすると、たかだか1勝分しか変化しない理由を言うのを忘れてた気がするけど、 例えば、a,b,c⇒a,c,bにしたとすると a, a+b, a+b+c a, a+c, a+b+c となり、2番目のとこだけ累積和が変わらない。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

antaさんついに。強い。

nico_shindannin（診断人） @nico_shindannin

一番勝数が多いケース（重い狐が先）から一番負数が多いケース（軽い狐が先）まで、0勝か1勝しか変化しないように、メンバー順をじわじわ変更できれば、とりうる勝数全てで、狐の並び方が見つかる。連続性?を使った面白い問題だと思いました

nico_shindannin（診断人） @nico_shindannin

2番目のとこだけしか累積和が変わらない（a+b≠ a+c）

nico_shindannin（診断人） @nico_shindannin

反省。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Demon判定正当性が結構怪しい気がしていたけど、2≦Aなのか。それなら自信あった。

nico_shindannin（診断人） @nico_shindannin

「2番目だけ累積和が変わる」とシンプルに言いましょう。

よすぽ @yosupot

@snuke_ ちなみに、A=1だとN=100, 0-1-2-3-...-99みたいな一列グラフでヤバイと思う(本来2個切ればいいけどかなり多重感のあるグラフが出来ませんか？)(これでマズそうなので僕は棄却しました)

nico_shindannin（診断人） @nico_shindannin

@snuke_ Demon判定、始点（or終点）からの辺を全部無効にする必要があるので、DがN-1以上では、ダメでしょうか？

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@yosupot 正解です👏 出なくてよかった（結果論）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

ってか今日ずっと頭がぼんやりしていて思考が出来ていない。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

探索の深さが１以上の思考が出来ていない感じ。マルコフ連鎖マシン状態。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@nico_shindannin 2≦Aを見落として適当に書いてしまっていて、でも2≦Aの時は正しいことは証明してから出したという感じです。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

2≦Aならmincutは必ずN-1になります。

JetBrains製IDEのパフォーマンスに生産性を握られている @konjo_p

提出したmedの嘘解法，自明の「じ」ぐらい自明に無理な解法だったのにどうしてコンテスト中これを実装しようなんて思ってしまったんだ．．．

JetBrains製IDEのパフォーマンスに生産性を握られている @konjo_p

解法の方針を立てるのを反例の発見に頼り切ってしまってるから起こる問題のように思えるけど．

JetBrains製IDEのパフォーマンスに生産性を握られている @konjo_p

解けるかどうかびみょい問題なんだから反例無かったら実装して提出するのが戦略的には良いんだよなあ．（どうせ自分より順位上の人からしか撃墜されんだろという見込みも含んで

lyoz @lyoz

practiceでmed通った．A>=2ってAngelが v \in 1..n-2 を通るようなパスを作れる(のでDemonはn-1箇所切らないと必勝にならない)っていう意味か

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

0≦Aでも解けた気になったので考えてみてください。