読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

TopCoder Marathon Match 93

最近ではすっかり英会話仲間なagwたんに再三誘われてたのもあり
久しぶりにMarathon Matchに出てみた話。

Marathon Match 93 (3/1 23:00EST〜3/16 0:00EDT)


最後に出たMMは4年前のTCO13らしい。
(問題文だけはとりあえず読んだもののあまり気乗りがしなくて参加に至らず、というのは何度かあった気がする。)

今回のMMの目標は、とりあえずyellow coderに上がること。(現在のratingは1424)

↓黙って出てたけど捕捉されてる


今回の問題は、与えられた多色(2〜20色)のパターンを、クロスステッチでできるだけ少ない糸で刺繍するという(いかにもTSPな)問題。
とはいえTSP(巡回セールスマン問題:Travelling Salesman Problem)を解くコードを自分で書いたことはなかったので良い機会になりそう。

初日

とりあえず公式ビジュアライザをDLして、(任意のseedの問題パターンをファイルに書き出すためのダミークラスを作って)問題パターンを手に入れる。
サンプルコードを動かして、少し自分でもいじってみる。

初期の方針

・上から単純に走査(左→右→左→右→…)
・盤面をNxNマスのブロック(というかウィンドウ?島?)というかで分割して、その中の接続と、他のブロックとの接続をTSPで。(N=Sでセル単位のTSP)
・(union-findで)接触するセル同士を島として、(あるいは1つ空けたぐらいなら同じ島に含めたりして)、(以下同じ)

自分用ビジュアライザを(Python+PILで)さくっと書いた。
f:id:n4_t:20170319111705p:plain
f:id:n4_t:20170319111726p:plain
f:id:n4_t:20170319111717p:plain

・とりあえず島の中心座標をもとにTSP。その後、島の上端・下端を用いたTSPを併用。
・TSPは辺と辺を交換するやつと、あるセル(1つ〜連続した沢山)を別の辺に移動するやつと。(2-optってのは前者?)
・出来上がった経路の最長辺を切って出来上がり →どのセルからもコスト0で行ける点を用意して始点&終点にすれば良いからそうした

この時点でスコアは43万前後。とりあえず50万は行きたい…

中期の方針

・水平方向に連続したセルのみのグループ化を試したり
f:id:n4_t:20170319112509p:plain
・島が大きくなると島から島への接続が非効率になってくるし、計算量多くてもセル単位TSPでいいんじゃないか、と思ってセル単位のTSPに絞ってコード書き直し
・セル間の接続は、セルの原点座標どうしの距離を基にTSP
・接続していく際にいちばんましなin/out位置を取っていく
・経過時間を取得してTSPを途中終了する(つもりでclock()をざくざく読んだら軒並みTLE;TopCoderサーバではclock()呼び出しは結構コスト高いのね)
f:id:n4_t:20170319113504p:plain

ローカルでのテストに、seed1〜100の入力のほか、最悪ケースを自作して追加。
ローカルのseed100までの平均で50万ちょい。
submitすると49万台。上位陣は51万超で戦ってる…

後期の方針

・精度上げるには、セルのどの角から入ってどの角から出るかも含めてTSPしたほうがいいか?(セル数x4)の2乗分の距離を計算する必要があるけどやってみた。greedyに取っていくんだけど、あるセルの1つの角が使われたら、次に使えるのはそこと隣接する角だけ、みたいな縛りで
・セルのどの角からどの角に入るかの情報をpathに含めた(時計回りで0,1,2,3;対角は必ず±2だからXOR 2で出せる。セル内でのステッチは入った角の両隣りのどちらかの角(±1)から出る。…)
・2-optで入れ替えする際には、もっと良い角があればそっちに回した
f:id:n4_t:20170319113922p:plain
f:id:n4_t:20170319113814p:plain

とりあえず、サーバ上で50万は出るようになった。
多分これ、焼きなましとかしていかないとトップ集団に追いつけないんだろうなと思ってたんだけど、どこをどう焼きなましたらスコアが上がるのか掴めなかった。距離にノイズを入れたり初期配置をランダムにしたりとか色々してみたけどスコアを上げられず。

終了時間ぎりぎりまでねばる、みたいな事はしてなくて(出来なくて)、いちばんましだったやつをsubmitして終了。
→ 最終投稿コード
https://gist.github.com/naoyat/e6336534425bf787731722a66af2d8b8


終了時点で19位。(このままを保てばratingは1500をわずかに上回る予想)

終了後

システムテストって結構時間かかるんだっけ…(1人につき1000件?)

agwたんによるまとめ
togetter.com

hakomo氏のコードめちゃ短い…(しかも前半戦で2投しただけでそのまま逃げ切ってるし)

kuuso氏の解説。そうかセル毎に✕✕(クロスステッチ)しててもこういうのには勝てなさそう

gorbunov氏の振り返り記事(@TopCoder公式ブログ)
www.topcoder.com
上位20人分だけ切り抜かれた"pre-final leaderboard"のキャプチャに登場してた