■ [MM]Marathon Match 54 
毎回参加しないかもと言いつつ結局参加しているマラソンマッチですよ。
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13897&pm=10474
4辺に色が付いたタイルがN*N個ある。そいつらを、接している辺の色ができるだけ同じになるように正方形に並べよ。
8<=N<=20、色の種類をCとすると10<=C<=30。完全解の存在は保証されている。
解法
とりあえず、Nが小さくてCが大きい場合は全探索DFSで完全解の探索が間に合うのでそれで。
見るからに焼きなましてくださいと言わんばかりの問題に見えたので、ひとまず焼きなましてみると80点くらい。
上位とは10点以上差があるので、どうしたもんかなと。
けれども特にいい方法も思いつかないので焼きなましをチューニングしていく。
当初の10倍くらい高速化したり温度の下げ方を調整したり2点交換じゃなく3点交換にしたり、
色々やったら90点をちょっと超えるくらいまではいった。けどそこから全然伸びなくなった。
トップは95点超えてたので全然違う方法が要るのだろうと、もう一度別のアプローチを考える。
焼きなましの初期状態を単純なgreedyで作ってたのをやめて、ある程度の時間DFSで部分最適解を探索してから一番良かったものを使う、としてみた。
すると、部分最適解自体が結構なマッチングを達成していて、焼きなましもそれなりに効いてぐんと伸びてくれた。93点くらい。
最後にちょっとチューニングして終了。結局、焼きなましの温度は時間に伴って下げない方がいい結果になった。そんなもんなんですかね。
ローカルテストでは95.5点くらい出てたのだけど、サーバーでの実行が予想よりもだいぶ遅いみたいでそこまで上がらなかった。
Forumを見ると、みなさん意外と探索でやっている。焼きなまし一択かと思ったのだけど、いろいろなアプローチがあったのだなあ。
結果
- 暫定スコア 94.25/100
- 暫定順位 15/262
なんとかレーティングのpercentileと同じくらいの位置に付けられた。これでレート下がることはないだろう。よかったよかった。いつまで単調増加続くかな。
…と思っていたら、バグを残したまま提出してることに気づいてしまった。100個に1個くらい例外吐いて落ちるやつがある。
ローカルテストでseed1-seed100しかテストしてなくて、その中にはこのバグが問題になるケースはたまたまなかったので気づいてなかった。
さらに、全探索をするNとCの値を見誤っていて、時間内に全探索が終わらずTLEしてるケースもある。これはだめだー。
サーバーでのスコアがローカルのより1点以上低かった原因は、速度ではなくてこれかもしれない。うーむこれはシステムテストで順位落ちるかもしれんな…。
【教訓】一度はたくさんのテストケースを通しましょう
追記
最終結果では順位上がって9位でした。
rating 1921 → 1993
0点のテストケースは1000個中4つしかありませんでした。入れちゃってたバグが問題になるようなケースは少なかったのか。
しかし、ちゃんとバグ潰してたらあと3.5点くらい上がってたはずで、そうすると5位だったのか。残念。また次回がんばりましょう。
