■ [MM][TCO]TCO09 Marathon Round2 
300人→100人。
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13767&pm=10357
何十個かのギアを、ひと繋がりになるようにくっつけつつできるだけ狭い領域に押し込める、という問題。
方針
最近マラソンのやり過ぎでいろいろとまずいので、ややこしいことはせずにお手軽にできる範囲で済ませたい。通過できると期待してもいないし。
plane数やギアの大きさを基に良くなりそうな配置を想定して並べることもできるかもしれないけど、それは大変そう。
まあランダムに置いてって一番いいやつを取る、くらいでいいんじゃなかろか？
履歴
| 日付 | 使った時間 | やったこと |
|---|---|---|
| 3/11（水） | 0.5h | 問題を読んだ |
| 3/12（木） | 2h | 自明解（一直線に並べる）でとりあえず提出。みんなも同じことやってるようで集団の中に入った |
| 3/13（金） | 6h | ギアを一組ずつ置いていくとき、その時点で面積最小になるようgreedyに位置を決めていくようにした |
| 3/14（土） | 7h | 金曜のやつを時間制限いっぱい繰り返してベストを取るように改良。 最初5個はランダムな向きに置いてから残りはgreedyに配置 |
| 3/15（日） | 3h | ランダムな向きに置くのは最初1個だけにしたとか、 スコアが同じでもできるだけ領域の内側向きに配置するとか、 planeはできるだけ直近に使ったやつを使い回すとか、微妙な改善をちまちま |
| 3/16（月） | 3h | ギアの大-小の組み合わせや並べる順番を、いろいろなパターン試すようにした。 大きい順とか小さい順とか、大小交互に並べるとか、ランダムとか。 手元のテストではスコア上がってるはずなのに提出すると下がった |
| 3/17（火） | 4h | 月曜に提出したやつにバグがあったことが発覚、修正すると期待通りに上がった あとは計算を少し高速化 |
| 3/18（水） | 2h | まだバグが残っていたので修正。するとスコア下がった… |
結果
暫定順位 85/238
100位付近は僅差で密集してるので最終結果はかなり変動しそう。テスト結果怖いよー
感想
そんな難しいことしていないわりには、それなりの結果でした。
ギアの並びはただランダムに試すんじゃなくて焼きなませばよかったのか。
フォーラムで「seed27とか95とかがキモいケースだけどみんな対応できてるか？」→「最低1～100くらいまではテストするだろ常識的に考えて…」みたいなやりとりがあってるけど、なんかめんどかったので1～10しかテストしてませんどうもすんません。
やっぱりそのくらいやった方がいいよなぁ。余力があるときはやろう。
