TopCoder Marathon Match 93
最近ではすっかり英会話仲間なagwたんに再三誘われてたのもあり
久しぶりにMarathon Matchに出てみた話。
Marathon Match 93 (3/1 23:00EST〜3/16 0:00EDT)
最後に出たMMは４年前のTCO13らしい。
（問題文だけはとりあえず読んだもののあまり気乗りがしなくて参加に至らず、というのは何度かあった気がする。）
今回のMMの目標は、とりあえずyellow coderに上がること。（現在のratingは1424）
↓黙って出てたけど捕捉されてる
naoya_tさんがMarathon提出してる
— 今年は夏バテにならない (@tomerun) 2017年3月5日
今回の問題は、与えられた多色（2〜20色）のパターンを、クロスステッチでできるだけ少ない糸で刺繍するという（いかにもTSPな）問題。
とはいえTSP（巡回セールスマン問題：Travelling Salesman Problem）を解くコードを自分で書いたことはなかったので良い機会になりそう。
初日
とりあえず公式ビジュアライザをDLして、（任意のseedの問題パターンをファイルに書き出すためのダミークラスを作って）問題パターンを手に入れる。
サンプルコードを動かして、少し自分でもいじってみる。
初期の方針
・上から単純に走査（左→右→左→右→…）
・＼／＼／｜と進んで／＼／＼で戻れば節約できるのでは？いや、裏面に抜けたのと同じ位置で表に戻ってこないといけない。刺繍的にはあり得るかもしれないが、今回のルールでは無しなのでは。無しだよね。（初期に異常な高スコアが出てた人たちはそうしていたらしい）
・盤面をNxNマスのブロック（というかウィンドウ？島？）というかで分割して、その中の接続と、他のブロックとの接続をTSPで。（N=Sでセル単位のTSP）
・（union-findで）接触するセル同士を島として、（あるいは１つ空けたぐらいなら同じ島に含めたりして）、（以下同じ）
自分用ビジュアライザを（Python+PILで）さくっと書いた。
・とりあえず島の中心座標をもとにTSP。その後、島の上端・下端を用いたTSPを併用。
・TSPは辺と辺を交換するやつと、あるセル（１つ〜連続した沢山）を別の辺に移動するやつと。（2-optってのは前者？）
・出来上がった経路の最長辺を切って出来上がり →どのセルからもコスト0で行ける点を用意して始点＆終点にすれば良いからそうした
この時点でスコアは43万前後。とりあえず50万は行きたい…
中期の方針
・水平方向に連続したセルのみのグループ化を試したり
・島が大きくなると島から島への接続が非効率になってくるし、計算量多くてもセル単位TSPでいいんじゃないか、と思ってセル単位のTSPに絞ってコード書き直し
・セル間の接続は、セルの原点座標どうしの距離を基にTSP
・接続していく際にいちばんましなin/out位置を取っていく
・経過時間を取得してTSPを途中終了する（つもりでclock()をざくざく読んだら軒並みTLE；TopCoderサーバではclock()呼び出しは結構コスト高いのね）
ローカルでのテストに、seed1〜100の入力のほか、最悪ケースを自作して追加。
ローカルのseed100までの平均で50万ちょい。
submitすると49万台。上位陣は51万超で戦ってる…
後期の方針
・精度上げるには、セルのどの角から入ってどの角から出るかも含めてTSPしたほうがいいか？（セル数x4）の２乗分の距離を計算する必要があるけどやってみた。greedyに取っていくんだけど、あるセルの1つの角が使われたら、次に使えるのはそこと隣接する角だけ、みたいな縛りで
・セルのどの角からどの角に入るかの情報をpathに含めた（時計回りで0,1,2,3；対角は必ず±2だからXOR 2で出せる。セル内でのステッチは入った角の両隣りのどちらかの角（±1）から出る。…）
・2-optで入れ替えする際には、もっと良い角があればそっちに回した
とりあえず、サーバ上で50万は出るようになった。
多分これ、焼きなましとかしていかないとトップ集団に追いつけないんだろうなと思ってたんだけど、どこをどう焼きなましたらスコアが上がるのか掴めなかった。距離にノイズを入れたり初期配置をランダムにしたりとか色々してみたけどスコアを上げられず。
終了時間ぎりぎりまでねばる、みたいな事はしてなくて（出来なくて）、いちばんましだったやつをsubmitして終了。
→ 最終投稿コード
https://gist.github.com/naoyat/e6336534425bf787731722a66af2d8b8
終了時点で19位。（このままを保てばratingは1500をわずかに上回る予想）
終了後
システムテストって結構時間かかるんだっけ…（1人につき1000件？）
agwたんによるまとめ
togetter.com
hakomo氏のコードめちゃ短い…（しかも前半戦で2投しただけでそのまま逃げ切ってるし）
わりとトリッキーで読みづらいと思いますが、最終サブミット（２９８行）です https://t.co/wKbgldGvgu
— hakomo (@hakomof) 2017年3月16日
kuuso氏の解説。そうかセル毎に✕✕（クロスステッチ）しててもこういうのには勝てなさそう
MM93の方針として連結成分に分けることの是非はともかくとして，4-connectedの必勝法です．ご査収ください． pic.twitter.com/eXRkuUiKHw
— kuuso (@kuuso1) 2017年3月17日
各セルの２ステッチ（＼／）を分解して別々に扱えば
こんな風に出来るのだけれど（必要な演算は島の上下端を用いてTSPした時と同じ）、
初期に＼／＼／みたいなの無しだよね、ってなってから、セルの分解そのものを思考から外してしまっていた。
◎gorbunov氏の振り返り記事（＠TopCoder公式ブログ）
www.topcoder.com
上位20人分だけ切り抜かれた"pre-final leaderboard"のキャプチャに登場してた
