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

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

ninja

ハル研究所プログラミングコンテスト 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

職人芸みたいな関数が好きです

この記事をシェア

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

関連する記事

2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase
2018年11月25日
CODE THANKS FESTIVAL2018参加記
mds_boy
2018年10月30日
競プロだけでは習得しづらいJava Stream API 【アドベントカレンダー 6日目】
mikit
2018年12月19日
ゾーマからの脱出〜後編〜
ran
2018年12月18日
ゾーマからの脱出~前編~
Meffi

活動の紹介

カテゴリ

タグ