ハル研コン2019の参加記
10/1~10/15に行われたハル研究所プログラミングコンテストに参加しました。
二次元グリッド上にいる複数のカメを操作して同じ盤面にあるエサを食べ尽くす速さを競う問題で、最終的に57,473ターンで18位となりました！
(30位までの人は参加賞としてモバイルバッテリーがもらえます)モバイルバッテリーを得ました！わーい！！！ pic.twitter.com/HDQd2D7H7j
— えすびて (@nbit0125) 2019年10月15日
問題概要
ハル研究所 プログラミングコンテスト2019 | 問題
ざっくり書くと、
- 60*30の盤面に複数のカメとエサがある
- 各ターンごとに各カメは上下左右に移動できる
- エサにはそれぞれ「高さ」という数値が指定されていて、エサのあるマスにその高さ以上のカメが集まると、食べることができる
- カメをうまく操作して、すべてのエサを食べるのにかかるターンを最小化せよ
という問題です。240個の異なる盤面に対する、エサを食べ尽くすのにかかったターンの合計でスコアが計算されます。
方針
（当然ですが）すべてのカメの動き方を一つひとつ探索していては時間が足りません。
「最終的に食べられるエサの順番」を決め打ちすると、その順番を守りつつ効率よく食べる操作列が作れそうだと考えました（例えば現在食べようとしているエサに対して、そのエサに近いカメから順に向かわせるなど）。
なので、基本的な方針として「エサの位置に2-optを使って移動経路が少なそうなエサの食べ方を求める」→「実際に掛かるターンを評価する」→「{ターン,順番}のペアをpriority_queueに入れる」→「queueから上位3つまでを取り出して順番を乱択で変える」→「再び評価してqueueに追加する」…というループを回すことにしました。
乱択をする際には（順番的に遠いものを入れ替えても改善する可能性が低いと考えて）、あるエサと、そのrandom(13)+1個隣のエサを入れ替えるようにしました。
また、「あるエサを食べて次のエサを食べに行く際、途中で別のエサを食べることができる」という場合があります。
なので、予め「エサa→エサbという順番で食べるとき、ついでに食べることができるエサ」をすべてのa,bに対して求めておいて、なるべく無駄がない食べ方をさせるようにしました。
やっていたこと
メモを取った
コンテスト開始からしばらくの間は、「自分が何をして、その結果どの程度改善したのか」のメモを取るようにしていました。
個人的にこれがすごい良くて、行き詰まったときに見返して改善が大きかったところを詰めたり、高速化する意味のなさそうなところを判断する指針になりました。
あと、日に日に書き込まれていくため、単純にモチベがとても上がります！
（ある程度）ちゃんとした変数名をつけた
今回のコンテストでは、ステージの生成部やシミュレーション部などのソースコードがはじめから公開されています。
普段僕はとても適当な変数名をつけがちなのですが、そのコードに習って、ある程度しっかりした変数名をつけるようにしました。
その結果、ある程度時間が立ってからコードを読んでも、どういう処理をやっているかが格段にわかりやすくなりました。
（ただ、終盤になってくると変数名と実態が一致しないみたいなことも起こって辛くなりました（は？））
感想
ハル研究所のプロコンには去年も参加していたのですが、その時は何一つ改善できないまま終わってしまったので、今回入賞できてとても嬉しいです。
問題もとてもわかりやすく、付属のソースコードやビューアもしっかりしていて、二週間夢中で取り組むことができました。
来年も参加したいです！
