Topcoder Open 2016 Marathon Match(Round 2)の参加日記
62位/183人の定位置だった。そろそろ一皮剥けたいものだ。
問題概要
- 二次元平面（1024x1024）に星が100~2000個ある
- 星の場所に、ランダムに船が1~10隻ある
- 星の場所に、ランダムにUFOが0~(星の数/100)個ある
- 1ターンごとに船を動かすことができる
- 1つのターンでいくつの船を、どの星に動かしても良い（同じ星もOK）
- 1つの星に何度でも到着してよい
- 星は、どの船でも1回以上訪れていれば、到着済みになる
- ただし、最初のターンに船がいる星は未到着扱い
- UFOも1ターンごとにランダムに動く
- 1ターンごと、UFOの現在地・次の星・次の次の星が与えられる
- ターン数の上限は星の数x4
- ターン上限までにすべての星が到着済になるよう、ターンごとに船に指示を与えるのが目的
- ただし、船の移動コスト合計はなるべく小さくしたい
- 移動コストは基本的に移動距離と同じ
- ただし、もし船の航路とUFOの航路が同じなら、移動コストは距離x（1/1000＾同航路のUFOの数）になる
- 星の位置は完全にランダムではない。いくつか(1~16)の銀河が存在し、星は各銀河の中心から正規分布している
- またUFOごとに飛び方に特徴がある。UFOは星を全体からN個ランダムに選んで、その中の最も近いものに飛ぶが、Nの値はUFO固有(10~10+星の数/10)
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16703&pm=14268
方針
- UFOが近く(距離100くらい)にくるのを待ってから乗る。なかなか来なかったら最も近いものに乗ってしまう
- 残りターンが少なくなるまで乗り続ける。同じ星に良さそうな別UFOがいたら乗り換える
- UFO未到着の星で巡回セールスマン（Nearest Neighborのあと、貪欲的に改善)
巡回セールスマンは焼きなましで組んでみたが、どうもうまく動かず断念した。
上位との比較
- 全体的な方針は一緒
- TS部分で大きな差がついていそう
- TSは焼きなましの人と、NNのあと2.5optなどTSP特有のアルゴリズムがいる
- 最上位の方たちは、UFOランデブーもかなり注意深いロジックを組んでいる。UFOの挙動から特徴を推定・シミュレーションして、gain/costを判断してたり
Psyhoさん(暫定1位)のコード http://pastebin.com/GQV4yrDj
（UFOランデブーではモンテカルロシミュレーション、TSでは焼きなましを使ってるらしい）
気づかなかったこと＋実装できなかったこと
- TSパートでもUFOが使えるのに気づかなかった（特に最初に１手）
- UFOから降りるとき、未到着の星の近くで降りのも良い考えだった
- 別UFOと重なったときの判断に、UFOごとの統計情報が使えた
- 最初の1手で船を動かさない場合、その星は到着済扱いだった
反省点
焼きなましを練習しよう。
