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

Topcoder Open 2016 Marathon Match(Round 2)の参加日記

C# Topcoder プログラミングコンテスト マラソンマッチ

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

方針

  1. UFOが近く(距離100くらい)にくるのを待ってから乗る。なかなか来なかったら最も近いものに乗ってしまう
  2. 残りターンが少なくなるまで乗り続ける。同じ星に良さそうな別UFOがいたら乗り換える
  3. UFO未到着の星で巡回セールスマン(Nearest Neighborのあと、貪欲的に改善)

巡回セールスマンは焼きなましで組んでみたが、どうもうまく動かず断念した。

上位との比較

  • 全体的な方針は一緒
  • TS部分で大きな差がついていそう
  • TSは焼きなましの人と、NNのあと2.5optなどTSP特有のアルゴリズムがいる
  • 最上位の方たちは、UFOランデブーもかなり注意深いロジックを組んでいる。UFOの挙動から特徴を推定・シミュレーションして、gain/costを判断してたり

Psyhoさん(暫定1位)のコード http://pastebin.com/GQV4yrDj
(UFOランデブーではモンテカルロシミュレーション、TSでは焼きなましを使ってるらしい)

気づかなかったこと+実装できなかったこと

  • TSパートでもUFOが使えるのに気づかなかった(特に最初に1手)
  • UFOから降りるとき、未到着の星の近くで降りのも良い考えだった
  • 別UFOと重なったときの判断に、UFOごとの統計情報が使えた
  • 最初の1手で船を動かさない場合、その星は到着済扱いだった

反省点
焼きなましを練習しよう。