ハル研究所プログラミングコンテスト2019 参加記
ハル研究所プログラミングコンテスト2019 に参加しました！
結果は暫定９位 *1 でした！
賞金圏内に入れなかったのは残念ですが、記念品のプロコン2019オリジナル“カメデザイン”モバイルバッテリーがもらえそうでうれしいです。
ちなみにハル研プロコンは今年で３度目の参加です。
問題の概要
概略は次のとおりです：
- ステージの盤面は (横, 縦) = (60, 30) のグリッド状のマス
- 初期位置として複数のカメとエサがマスのどこかに配置
- 各エサには高さ h のパラメータがあり、同じ瞬間にh個のカメがそのマスにいるときのみ、カメたちはそのエサを食べることができる
- 各カメは各ターンに上下左右のいずれかの方向に1マス移動可能（動かなくても可）
- エサをすべて食べ終えるとそのステージはクリア
- ステージは全部で240個あり、カメをうまく動かすことで各ステージに要したターン数の合計を最小化しなさい
実行時間の制限は60秒で、1ステージ当たり平均0.25秒以下で計算する必要があります。
配送計画問題の亜種みたいなシンプルな問題ですが、エサを消費するために複数のカメが同時にそのマスにいる必要があるという条件が問題を複雑にしています。
大まかな解法
↓ 最終的に実装した大まかな解法です。
- エサをk-means++でクラスタリング
- クラスタ内とクラスタ間でそれぞれTSPをしてエサの順序を決める
- 先頭の数個で順列を回しながら貪欲にカメを割り当てる
- 対象のエサへの経路に余裕があるカメをつかって近傍のエサを回収させる
- 実際にシミュレートしてターン数が少ないパターンを採択
- その他、色々なヒューリスティック
クラスタリング+TSP+貪欲(+順列)+シミュレート+ヒューリスティック です。
思考・方針の過程
以下に考えたことややってきたことなどを書いていきます。
また、方針の大きな変更が２度あったのでそれぞれ方針1,2,3とします。
前提・準備
まず、問題文をよく読みました。長期コンテストで誤読やレギュレーション違反に気づかないまま中盤まで継続すると非常につらいことになるのでこれは必須事項です。
次に与えられたソースコードを軽くリーディングしました。特に重要なのはアクセス可能な変数や定数とステージの生成方法の２つです。
hpc::Parameter: スタージの大きさやカメ・エサの最大数などの定数が定義されているhpc::Stage::initialize: ステージ生成hpc::Game::run: ステージ生成に必要なパラメータの生成
コードを読む限り、考察する上で大事そうな部分を抜粋すると：
- カメやエサの初期配置は一様分布
- 互いの初期位置が重なることはない
- エサの高さはパラメータ
distributionに依存distributionが大きいほど、小さい高さになりやすい- 高さの最大値はそのステージのカメの個数
- 各ステージ生成パラメータは、ステージのインデックスに対して周期的に決まる *2
という感じでした。
方針1
「高さの最大値はそのステージのカメの個数」を踏まえると、すべてのカメが同じマスにいないといけないターンがいくつか存在することがわかります。 「あるカメには右側を担当で別のカメには左側を担当」みたいなことはできないので、まずは大まかなエサの順番を決めて、その順番に貪欲にカメを誘導させることにしました。
とりあえず、左側のエサから順番に食べるという方針で実装しました。
適当にヒューリスティックなどを混ぜた結果のスコア：
- Local: 86,653, Remote: 85,800 (4.3046 sec) *3
ビューアからわかるように無駄がまだまだ多いです。
方針2
方針1では1列ずつ左側から処理しているけど、ある程度幅をもって辿らせると良さそうと思って方針を変えました。
盤面を5×5の大きさのエリアに分割して左側から上下にジグザグに辿るように変更しました。
- Total turn: 76,880, Remote: 76,317 (4.3281 sec)
まあまあ伸びた気がします。
ビューアで観察したところ、エサの位置に偏りがある場合はうまく対応できてないのが確認できました。
方針3
というわけで、偏りがあってもうまくできるようにしようということで、エサの位置に関してクラスタリングすることを考えました。その場合、クラスタごとの順番が自明ではないのでとりあえずTSPをします。
- クラスタリングにはk-means++
- TSPには
- サイズが小さい => 動的計画法
- サイズが大きい => 近似手法
- 構築: NN, Greedy, DMSTをそれぞれやって一番良いものを採択
- 改善: 2-opt, or-opt
さらに思いついた色々なヒューリスティックを混ぜます：
- クラスタの重心計算に対して、エサの高さで重み付け
- ソートの比較関数を†いい感じに調整†
- など
この時点でのスコア：
- Local: 62,653, Remote: 62,388 (3.2812 sec)
30位以内に入りました✌
こっから勢いが乗ってきたのでスコア伸ばしていきます。
20位になった pic.twitter.com/g3TCG94sLv
— Ark (@arkark_) 2019年10月12日
6万切ったhttps://t.co/MQETdheehz pic.twitter.com/HLiqYflGWF
— Ark (@arkark_) 2019年10月13日
例えば、ヒューリスティックに対するマジックナンバーがいくつかあり適切な値の設定がむずかしいため、実際にステージのシミュレートしてターン数を計算し、少ないターン数になった方の値を採択ということをしました。
- Local: 58,421, Remote: 58,199 (7.5546 sec)
だいぶスコアも伸びたため、そろそろ時間を使うフェイズに入ります。
これまではエサの順序を確定した上でカメを割り当てていましたが、先頭の数個の順列をすべてためして推定ターン数が少ないものを採択をやりました。さらに、ステージ上のエサの状態が変わったターンのみ計算することで高速化をはかりました。
最終的なスコアは：
- Local: 55,818, Remote: 55,297 (59.8906 sec)
となり、9位で終了しました！
感想戦
ハル研プロコン終了後、参加者たちが解法ツイートをしていました。解法が色々あっておもしろいです。
いくつかツイートを拝借しますm(__)m
やったこと：
— くれない。 (@kurenai3110) 2019年10月15日
ChokudaiSearchで大まかな流れを作ってから山登り
ChokudaiSearchが全体で10秒、残りの時間で山登り
ハルコン2位でした やったこと：
— 実装をしない (@shr_pc) 2019年10月15日
解の表現：
エサを食べる順序で表現。各カメの位置と行動可能時刻を管理し、次に食べるエサに最も早く集まれるカメたちを順に動かしていく
順序の決め方：
エサの位置、高さ、カメとの距離、…などを元に評価関数を作成、評価の高いエサから順に4～6個を試す→
ハル研コンお疲れ様でした
— c7c7 (@C7C7LL) 2019年10月15日
真ん中よりも少しずれた位置 ( x=20 , y=15 ) あたりに亀を集めて時計周りに餌を食べる
亀の割り当てはその餌に来れる早さで貪欲
餌を食べる順番を2始点山登り
遷移はランダムな位置にランダムな餌の挿入。
後なんか色々高速化した sortをnth_elementにして log を消したり等
ハル研プロコン4位でした
— 💩 (@lgeuwce) 2019年10月15日
高さがカメの数の半分より大きいエサの巡回セールスマン問題をheld-karp下界を使った枝刈りで解いて、それらのエサを食べる順番が守られる制約をつけてchokudaiサーチ、最後にエサ順列からにエサを一つ選んで近い別のところに挿入する焼き鈍しをしました pic.twitter.com/W76TaozPuQ
ハル研プロコン
— daisyo (@dsytk7) 2019年10月15日
「コ」っぽく回るように初期解を生成。
餌を食べる順番を焼き鈍し。
遷移は適当な餌に近い餌を次の順番に挿入する。
みたいなことをやっていた。
ハル研プロコン9位でした：
— Ark (@arkark_) 2019年10月15日
k-means++でクラスタリング, クラスタ内と各クラスタでTSP, 先頭の数個で順列回しながら貪欲, 実際にシミュレートしたものを評価関数, foodの状態が変わったターンのみで計算, 大正義ヒューリスティック
さいごに
ハル研プロコンたのしい！
来年こそは5位以内に入りたい。
追記
いえい pic.twitter.com/VHy6TIP4gd
— Ark (@arkark_) 2019年11月29日