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

2018/10/04~2018/10/18の14日間にわたって行われたハル研究所主催のオンラインコンテスト「ハル研究所プログラミングコンテスト2018」に参加しました。

10/20時点で最終結果は発表されていませんが、コンテスト中のランキングの感じを見るに50位より下のはずです（何人参加したんでしょうか）。30位以上で入賞だったので結構遠くて悔しいです。チャレンジスコアは一応超えていました。

20×20の盤面にクッキー生地を置いて焼きます。生地には形と焼き上がり時間とスコアが設定されていて、1000ターンでスコアを最大化することを目指します。生地は大小それぞれ次の8個しか見えないことに注意。

ビームサーチをしました。盤面が400マスあって、全部見ていると多いので、BL安定点のみを探索することである程度高速化したりしました。大きい生地だけでビームサーチをすると何も置けなくなるターンが来るので、その場合は今置いてある大きい生地の中で一番早く焼きあがるものよりも早く焼きあがる小さい生地を適当に置きました。

今回は反省点が多い感じの結果になりました。

• 一番の反省点は、この問題自体を3次元packingに帰着できることに最後まで気づかなかったことだと思います。「2次元packingであることはわかってて、でもpackingは基本的に長方形が消えることはないので、そのへんを工夫する問題なのかな」→「よく見るとスケジューリング問題っぽい面もあるな」くらいの認識で最後まで行ってしまいました。時間軸も考えると3次元になって非常にすっきりするというのが本質だったようです。
• 後半はツモをランダム生成してビームサーチしていたんですが、やればやるほどスコアが落ちていって大変でした（ありうるツモのパターン数が多くて、それによって最適解が全く変わってくるのでむしろやらないほうが良かったという感じだと思います）。
• 評価関数についての考察が全く足りていませんでした。「焼き上がりが速い生地は高得点」以上の評価関数を思いつけなかったのはかなり悪いです（スコア自体を評価関数にするのは焼き上がり時間よりかなり悪かったです）。上位者は壁や他の生地と接する長さなどを使ったりしていたようです。
• まともに考察できていない状態でパラメータ調整をやり始めるのは意味が無いのでやめるべきだと思いました。

C++のプロジェクトをビルドするタイプのマラソンは初めてだったので勉強になりました。結果は少し残念でしたが、実戦でビームサーチを書いたのは初めてだったので練習としてはよかったと思います。来年も多分参加権限があるのでリベンジしたいです。