Ark's Blog

数学とか競プロとか参加記とか備忘録とか

ようこそ

ハル研究所プログラミングコンテスト2018 参加記

ハル研究所プログラミングコンテスト2018 に参加しました! www.hallab.co.jp

去年の参加記事はこちら↓

今年の問題

レーンに流れてくる大小の生地をオーブンに配置し、最終的に焼けたクッキーのスコア総計を最大化する問題。

与えられる情報は以下の情報のみ

  • オーブンの状態
  • レーンに置かれた大きい生地8個
  • レーンに置かれた小さい生地8個
  • (生地生成に関する確率分布)

制限時間が60秒なので実行時間にも気をつける必要がある。

  • 詳しい問題の内容についてはこちら

結果

https://www.hallab.co.jp/progcon/2018/result/

  • 順位:23位(学生18位)
  • スコア:2,562,220
  • 時間:52.9531秒

f:id:ark4rk:20181117233718g:plain

  • (このViewerはハル研の方が準備してくださいました。)

基本戦略

  • 20 * 20 * 1000 の3次元配列で、生地の配置情報を保持。
    • 最初に生地情報がすべて与えられ、各ターンで何個でも生地を配置できる場合は3次元パッキング問題。
  • 大きい生地の配置を決定したあと、その隙間に小さい生地を配置する。
    • 大きい生地を配置したほうがスコア効率が良い。
  • 配置決定方法は、「配置の順番」で探索
    • 各「配置の順番」に関しては貪欲+ヒューリスティックでそれっぽい評価関数を計算
    • 一番評価関数が高かったものを選択

詳しくは下のソースコードを見てください

感想

今回の問題の一番の難点は「最初にすべての生地の情報が得られるのではなく、逐次情報が追加される」という点でした。今後得られる生地情報がわからないので、どうしても「確実に改善する手法」が思いつきにくく、ヒューリスティックに頼り切りになってしまいました。

「これなら改善する」と思って実装したらスコアが下がったり、「こんなんじゃダメだと思うけど一応実装してみるか」で一気にスコアが上がったりと、なにがなんやらという感じです。

とは言っても、工夫できる部分はたくさんあり、実装の随所に"思いつき"を取り入れることで最終的なスコアは256万を超えました。順位もなんとか30位圏内に入ることができ、うれしいです。

記念品に「プロコン2018オリジナル“クッキー”マグネット」をゲットです!

来年はもっと上位を目指します!

ソースコード

ソースコードです。

(最初のアスキーアートが横幅で潰れてる・・・)