ハル研究所プログラミングコンテスト2013参戦記

ここ1ヶ月ぐらい「ハル研究所プログラミングコンテスト2013」に参加してました
締切時のスコアは410万点ほどで、27位ぐらいでした(うろ覚え)

<基本方針>

貪欲法です。以下の動作をInit関数内で済ませます
1.まだ選んでないゴミの中で、現在地から最も少ないターン数で到達できるゴミを選ぶ
2.選んだゴミを記録し、現在地をさっき選んだゴミの位置に更新する
3.まだゴミがあるなら1に戻って繰り返す

<穴の対処方法>

現在地と目標のゴミの位置を結ぶ線分の式を作り、全ての穴に対して交差判定を行います
交差していた場合、下図のように中継点を作り、迂回します
また、現在地と中継点を結ぶ線分、中継点と目的のゴミの位置を結ぶ線分に対しても同じ処理を行います
これにより、複数の穴があっても華麗に避けてくれます(たぶん)
詳しくは下の資料で


<ちょっとした工夫>

ゴミとルンバ自機には半径があり、少しでも触れていれば拾ったことになります
そのため、下図のように動き、ちょっとだけショートカットを図っています

f:id:negi_magnet:20140108221401p:plain

<試したけど使わなかったアルゴリズム>

ユークリッドTSPの近似解法
 回転にターンが必要なければユークリッドTSPの近似解法を適用できると思い、とりあえず作ってみました
 380万点ぐらい止まりだったのでボツ
 やはり回転をいかに抑えられるかが勝負所…?

・n個のゴミを最小ターンで取れるようにゴミを選ぶ
 貪欲法よりはマシかなーと思ってたらnを増やすほどスコアが減りました


こんな感じでした。楽しかった(小並感)
上位陣のアルゴリズムが知りたい…