ハル研究所 プログラミングコンテスト2019 参加記
ハル研プロコン2019に参加しました！
昨年に続き2回目の参加です。
去年の記事
ハル研究所プログラミングコンテスト2018 参加記 - NOSSの雑記
問題
- 30 * 60マスの広場にランダムにカメとエサが配置される。
- カメは1ターン毎に上下左右に移動できる。
- エサには高さが設定されており、エサの位置にその高さ以上の数のカメが集まったときエサを食べることができる。
- すべてのエサを食べるまでにかかったターン数がそのステージのスコア。
- 240ステージのスコアの合計を競う。
- 制限時間60秒
結果
結果は16位でした。 最終スコアは 57,109 です。
基本方針
基本的に「エサをどの順番で回収するか」と「カメをどのエサに向かわせるか」の2つをどう改善するかをコンテスト期間中試行錯誤しました。
最終的なプログラムでは、カメの中心付近を始点とするエサの巡回セールスマン問題の解を経路として、カメをエサに近い順に貪欲に向かわせるという方針になりました。
エサの経路
ステージによってはほぼ全てのカメを集めないと回収できないエサが大量に存在していることがあります。これらの高いエサを抜き出すと巡回セールスマン問題そのものになるのでエサの経路構築もこの要領でかなり改善できると考えました。
また、カメが集合することを考えると中央付近のほうが有利なのでカメの中央付近を始点として固定しました。そこにある高さ以上のエサを抽出して巡回セールスマン問題を解きました。近似解を得る方法は先に時計回りにまわる経路をつくって2-optで経路長を最小化するように焼きなましをしました。
その後、残った低いエサをNearest Insertionの要領で経路に挿入したものを最終的なエサの経路としました。
カメの割り当て
いろいろ試した結果、経路順に見ていって各エサからみて最も近いカメをそのエサに貪欲に割り当てるという方法が最もターンが短くなりました。他のエサに向かったカメもエサが回収される時刻を考慮して次のエサに向かえるか考慮したり、エサの回収時刻が遅くならないようになるべく遠くのカメを割りあてることをするとスコアが改善しました。
この方法だと経路のシミュレーションをカメの数をN、エサの数をMとしてO(MN logN)くらいでできるのでこれをもとに経路の評価をしました。
プログラム全体
最終的に制限時間のほとんどを最適な経路構築に使いました。抽出するエサの高さの全探索、始点の中心位置をランダムにずらす、で一番大きいステージだと2500回くらい経路を作ってシミュレーションしたターン数が最も短いものを採用しました。終盤はいずれかのエサが回収されたときだけカメの移動先を更新する、関数への引数の渡し方、など細かい高速化をして試行回数を稼ぐようにしていました。
感想
viewerを眺めながら次の改善案を考えるのが楽しい問題でした。2-optや焼きなましをコンテスト中に書けたのは初めてだったので去年の頃より成長できたなと思います。
ハル研の皆さんコンテストありがとうございました。また来年参加したいと思います！
