■ [MM]Marathon Match 55 
Marathon中はテスト回してるせいで部屋が暑いです！
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13923&pm=10475
炭坑の地図が与えられるので、トロッコの動きを上手くスケジューリングしてできるだけ早く掘ってたくさん石炭を回収してください、という課題。
解法
とりあえず
試行錯誤しつついくつか改良
- 微妙に時間が足りてないケースがあったので高速化
- 同じ距離にある石炭の中では、一度にたくさんdrillで崩せる箇所を優先する
- トロッコに半分以上石炭を積んでいる場合は、回収用エレベータに近い位置を優先的に取る
- 他のトロッコがターゲットに予約している石炭でも、もっと早く取れる場合は横取りする
これで上位1割くらいの位置。
さらに改良
- 10000ターンで強制終了なので、終了直前では掘りすぎないようにして、トロッコがいっぱいになっていなくてもエレベータまで戻るようにした
- 狙う石炭を探索するときのシミュレーションで、同一ターン内でのトロッコの動く順番も考慮するようにした
これで10位以内。
取っておいた策を投入
- BFSの探す順番が「右→左→上→下」固定だったのを、時間が許す限り他の順番も24通り試すようにして、一番いい結果になるものを採用する
- 同じ優先度のものがあったときの解決に微妙に影響する
- 上位は拮抗していたのでその微妙なところが重要なのです
- それでもまだ時間が余っている場合は、探索の関数を少し変えたものを何通りか試す
- ビット演算使いまくって極限まで高速化
この最後の一押しで一時暫定2位→ちょこちょこ抜かれて終了。
効果がありそうだと思ったけどできなかったこと
- 全く石炭がなくなった領域は探索しに行かないようにして高速化
- 実装はしてみたものの、バグってたせいか実際に意味がないせいか、効果が見られなかったので断念
- 1000ターンくらいで時間を区切る。何通りかの戦略を試してその時点での最良ケースを採用→そこから始めて次の1000ターンをまた何通りか試す… を繰り返す
- TCO09 Round3でやったようなこと
- タイムリミットの管理が難しそうだったので実装できず
結果
- 暫定順位 6/131
8位以下とはけっこう差があるので、7位以上は確定と思ってよさそう。3回連続で一桁順位か。最近調子いいなあ。
しかしいよいよレーティングが上がらなくなってきました。ここまでくると5位以内くらいは取らないと満足に上昇しなさそうです。厳しいな…。
