ハル研究所プログラミングコンテスト2018 参加記
ハル研究所プログラミングコンテスト2018 に参加しました! www.hallab.co.jp
去年の参加記事はこちら↓
今年の問題
レーンに流れてくる大小の生地をオーブンに配置し、最終的に焼けたクッキーのスコア総計を最大化する問題。
与えられる情報は以下の情報のみ
- オーブンの状態
- レーンに置かれた大きい生地8個
- レーンに置かれた小さい生地8個
- (生地生成に関する確率分布)
制限時間が60秒なので実行時間にも気をつける必要がある。
- 詳しい問題の内容についてはこちら
結果
https://www.hallab.co.jp/progcon/2018/result/
- 順位:23位(学生18位)
- スコア:2,562,220
- 時間:52.9531秒
- (このViewerはハル研の方が準備してくださいました。)
基本戦略
20 * 20 * 1000
の3次元配列で、生地の配置情報を保持。- 最初に生地情報がすべて与えられ、各ターンで何個でも生地を配置できる場合は3次元パッキング問題。
- 大きい生地の配置を決定したあと、その隙間に小さい生地を配置する。
- 大きい生地を配置したほうがスコア効率が良い。
- 配置決定方法は、「配置の順番」で探索
- 各「配置の順番」に関しては貪欲+ヒューリスティックでそれっぽい評価関数を計算
- 一番評価関数が高かったものを選択
詳しくは下のソースコードを見てください
感想
今回の問題の一番の難点は「最初にすべての生地の情報が得られるのではなく、逐次情報が追加される」という点でした。今後得られる生地情報がわからないので、どうしても「確実に改善する手法」が思いつきにくく、ヒューリスティックに頼り切りになってしまいました。
「これなら改善する」と思って実装したらスコアが下がったり、「こんなんじゃダメだと思うけど一応実装してみるか」で一気にスコアが上がったりと、なにがなんやらという感じです。
とは言っても、工夫できる部分はたくさんあり、実装の随所に"思いつき"を取り入れることで最終的なスコアは256万を超えました。順位もなんとか30位圏内に入ることができ、うれしいです。
記念品に「プロコン2018オリジナル“クッキー”マグネット」をゲットです!
来年はもっと上位を目指します!
わーい(>ω<) pic.twitter.com/9ZDPYoVXhj
— Ark (@arkark_) 2018年11月16日