GCJ 2019 R3

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

B：方針を正しく選べばかなり実装軽い。 C：単純に面白い。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

A：できるだけ2e10の区間を作ろうとする。終盤で2e10の区間が１個でも残ってれば自分だけ選択肢があるという状況が作れるのでまぁ勝てる。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

B：まずピラミッドの頂上は最大値にするのが最善。高さをp[i]に揃えるものがどういうものかに注目する。iの左にあってp[i]以上かつ最も右にあるものをp[l]、同様に右にあって〜をp[r]とする。左端を l 以下、右端をi~rの間にした時のみl~iの間にあるものの高さをp[i]に揃えることになる。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

C：辺に三叉路が２個以下しかなければ大体よくて、構築は三叉路から壁を辿って、十字路に来たら好きな方に曲がる。ただしすでに連結なところを連結にするようには曲がらないようにする。（三叉路がない場合は適当なところからスタート）（辺を全部辿れなかったら-1）

Япон Бүресе🏴‍☠️ @southerwolfie

@snuke_ 辺って何の辺

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@southerwolfie 最初の"辺"は盤面の辺で、後の"辺"は壁（ごめん）

Япон Бүресе🏴‍☠️ @southerwolfie

@snuke_ 盤面の辺って連結成分をなんか潰して全域木を作りたいやつの辺ですか

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@southerwolfie 盤面のふち。端っこ。

Япон Бүресе🏴‍☠️ @southerwolfie

@snuke_ 証明大変そうだなあ

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@southerwolfie 帰納法のイメージ。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

Cもっとシンプルにできたのか。 AAA ABA AAB とか BAA ABA AAB とかでBを孤立させそうと思ったけど、上はすでに連結だからAを繋がないし、下はそもそも不可能なのか。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

おまけ（サンプルとして使ったやつ） 1 7 7 AAABBBB ABBAAAB ABABBAB ABBABAB ABABABA ABBABBA AAAAAAA pic.twitter.com/I7iAm3NgSU

拡大

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

うーん、BC通せたのはよかったけど、Aが永遠にデバッグできなかった。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

まぁAを30分かけてすら通せなかったのがダメだった。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

あー、Aが永遠にバグる原因がわかった。wを読み込んでない・・・（リッチなinteractive_toolが欲しかった）（タイムアウトを設定する改造だけして満足してた）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

いや、最初のpが300になってるのは見てて、それを「すごい乱数シード見つけたなぁ」くらいの感想でスルーしてしまったのが頭悪すぎるんだよな・・・

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

くそなぞなぞ：メッチャくそなものってなーんだ？ 答え：毒素（ドくそ）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

やたら濃い腕毛が生えていたので切りました。