ハル研究所プログラミングコンテスト 2018に参加しました[アドベントカレンダー2018 40日目]
この記事はtraP Advent Calendar 2018 40日目の記事です。
こんにちは、ninjaです。12月はまだ始まったばかりですが、このアドベントカレンダーは後半戦です。
ハル研究所プログラミングコンテスト
最近アップデートの第3弾が配信された星のカービィ スターアライズはプレイしましたか？まだプレイしていない方は是非ともプレイしましょう。
それはさておき、星のカービィシリーズなどで有名なハル研究所は、毎年学生向けにプログラミングコンテストを開催しています。今年は10月4日から2週間で行われ、11月15日に結果が発表されました。
毎年、30位以内に入ると記念品をいただくことができるのですが、ギリギリ29位で記念品をいただきました。わーい
問題
大きさ(幅/高さ)と焼き上がりにかかるターン数、焼き上がったときのスコアをパラメータとして持ったクッキーが与えられるので、それらの配置を最適化して得られるスコアを最大化するという問題でした。
ただし、選ぶことのできるクッキーは制限されており、大きいもの8個と小さいもの8個でそれぞれを消費すると新しいものが補充されます。(このような逐次入力が与えられるものをオンライン問題といいます)
考察
クッキーのパラメータはばらつきがあり、それらの中から良いものを選んでいけば良いように見えます。しかし、実際には置かないという選択ができるクッキーは大小でそれぞれ8つ(最後に残るもの)しかなく、体積比(スコア/高さ*幅*時間)でみるとそれほど差がありません。そのため、クッキーを置く置かないという選択よりも、いかに多くのクッキーを配置できるかを考える方が良いスコアが出せると考えられます。
なので、クッキーを置いたときに他のクッキーをたくさん置くことができるようなクッキー、配置を探索する戦略を立てました。
解法
最初の配置をやきなまし法によって2次元での密な解を求め、その後はもっとも他のクッキーを含めて配置できるクッキーの配置を都度探索しました。
結果
スコア: 2,554,959
時間: 4.7187(sec)
で29位でした
このような結果が見れるviewerが同梱されています。
感想
参加するのは今年で3回目だったのですが、今のところ全て記念品をもらえているので来年も……という気分になりました。オンライン問題はほとんど解いたことがなかったので、なかなか取り組みにくかったのですが結果を残せたのでよかったと思います。
記念品のマグネットです。
明日はhukuda222さんが担当です。たのしみ〜
