ハル研究所 プログラミングコンテスト2018
10月4日から10月18日まで開催されていたハル研究所 プログラミングコンテスト2018の結果が発表されました。 ハル研プロコンへは4回目の参加でしたが、今回はスコア2,513,951で45位になりました。
今年の問題は、20×20のオーブンに様々な大きさ、所要加熱時間の矩形のクッキー生地を並べてスコアを競うものでした。 サンプルとして付属していた、座標(0, 0)に生地を置き続けるコードのスコアは36,049でした。
チャレンジスコアは2,450,000に設定されており、サンプルからはかなり遠いようにも見えますが、少し貪欲法を弄ると2,000,000くらまでは案外楽に到達することができます。 しかし、そこから先は、コードを改良してもスコアの上昇が小さく、思い通りにいかないもどかしさが募りました。
コンテスト中に実装した主な方針とその結果をまとめました。
| 方針 | スコア | 時間 (秒) |
|---|---|---|
| スコアの高い生地を左上から詰めて置く。 | 1,847,605 | 0.1406 |
| スコアの高い大きい生地を左上から詰めて置く。 | 2,163,827 | 0.1640 |
| 大きい生地を置く場所を予め決め、重ならない場所に小さい生地を詰めて置く。 | 2,480,109 | 2.4687 |
| 生地置き場にある生地の形状に応じて左上から詰めるときのx, yループの順序を変える。 | 2,513,951 | 2.6953 |
| 置き場所の予約を廃止。かわりに、オーブンにある大きい生地より焼き上がりが遅い小さい生地を置かないようにする。 | 2,448,679 | 0.1093 |
限られたターン数（1000）の中でスコアを最大化するためには、オーブンに無駄な空きをつくらないことが重要になります。 オーブンは2次元のグリッドなので、ステージ全体では3次元空間に直方体を詰める問題になります。 このことには早い段階で気づけたため、初めのうちはデータ構造や判定のための関数を整備していました。 しかし、いざ生地の配置を探索するとなると、有効な方針を考えられず、残念な順位に終わってしまいました。
優勝者の解説によると、箱を充填する問題を解くアルゴリズムとしてBottom-Left法というものが存在するそうです。 コンテスト中に検索していても、これにたどり着くことができなかったので、勉強になりました。
ハル研究所プログラミングコンテスト2018に参加しました – EL-EMENT blog
ハル研プロコンでは、思いついた方針を面倒がって実装せず後悔することが多かったのですが、今年は実装に力を入れたかいあり、考察力と知識の限界まで発揮できたと感じます。 しかし、それでも記念品圏内（上位30位）に入ることは叶いませんでした。 学生（とハル研社員）限定であるハル研プロコンに参加できるのは来年が最後であるため、絶対に入賞します。
