feature image

2018年12月3日 | ブログ記事

ハル研究所プログラミングコンテスト 2018に参加しました[アドベントカレンダー2018 40日目]

ハル研究所プログラミングコンテスト 2018に参加しました[アドベントカレンダー2018 40日目]

この記事はtraP Advent Calendar 2018 40日目の記事です。

こんにちは、ninjaです。12月はまだ始まったばかりですが、このアドベントカレンダーは後半戦です。


ハル研究所プログラミングコンテスト

最近アップデートの第3弾が配信された星のカービィ スターアライズはプレイしましたか?まだプレイしていない方は是非ともプレイしましょう。
それはさておき、星のカービィシリーズなどで有名なハル研究所は、毎年学生向けにプログラミングコンテストを開催しています。今年は10月4日から2週間で行われ、11月15日に結果が発表されました。
毎年、30位以内に入ると記念品をいただくことができるのですが、ギリギリ29位で記念品をいただきました。わーい

問題

大きさ(幅/高さ)と焼き上がりにかかるターン数、焼き上がったときのスコアをパラメータとして持ったクッキーが与えられるので、それらの配置を最適化して得られるスコアを最大化するという問題でした。
ただし、選ぶことのできるクッキーは制限されており、大きいもの8個と小さいもの8個でそれぞれを消費すると新しいものが補充されます。(このような逐次入力が与えられるものをオンライン問題といいます)

考察

クッキーのパラメータはばらつきがあり、それらの中から良いものを選んでいけば良いように見えます。しかし、実際には置かないという選択ができるクッキーは大小でそれぞれ8つ(最後に残るもの)しかなく、体積比(スコア/高さ*幅*時間)でみるとそれほど差がありません。そのため、クッキーを置く置かないという選択よりも、いかに多くのクッキーを配置できるかを考える方が良いスコアが出せると考えられます。
なので、クッキーを置いたときに他のクッキーをたくさん置くことができるようなクッキー、配置を探索する戦略を立てました。

解法

最初の配置をやきなまし法によって2次元での密な解を求め、その後はもっとも他のクッキーを含めて配置できるクッキーの配置を都度探索しました。

結果

ハル研究所 プログラミングコンテスト2018 | 結果発表

スコア: 2,554,959
時間: 4.7187(sec)
で29位でした

cookie

このような結果が見れるviewerが同梱されています。

感想

参加するのは今年で3回目だったのですが、今のところ全て記念品をもらえているので来年も……という気分になりました。オンライン問題はほとんど解いたことがなかったので、なかなか取り組みにくかったのですが結果を残せたのでよかったと思います。

iJ0zLg1p-1
記念品のマグネットです。


明日はhukuda222さんが担当です。たのしみ〜

ninja icon
この記事を書いた人
ninja

競技プログラミングなどをします

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】 feature image
2018年11月3日
ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】
Azon icon Azon
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
2021年4月25日
CPCTF2021 作問者writeup by xxpoxx
xxpoxx icon xxpoxx
2018年12月23日
LogicProXでのサラウンド設定,オーケストラ用テンプレ作成,その他の小ネタ
SolunaEureka icon SolunaEureka
記事一覧 タグ一覧 Google アナリティクスについて