問題の特徴

今年の問題は、限られたオーブンのスペースでなるべく多くのクッキーを焼く、という配置を効率化する問題でした。

問題の制作過程では、クッキーがおかしな形になったり、オーブンの火力が強くなったり、と紆余曲折ありましたが、最終的には大小2レーンに流れるクッキーを1つのオーブンで焼くという、シンプルな形に収まりました。

問題自体はシンプルですが、未来の予測が困難で、高得点をとるには難易度の高い問題だったのではないかと思います。

オーブンがある程度埋まるまでは点数が伸びやすいですが、クッキー同士が干渉し始めるととたんにスコアを伸ばすことが難しくなり、干渉を回避するために配置の調整、探索、確率予測といった様々な工夫が必要になる問題だったと思います。

作品の傾向

「プロコン速報 vol.1」のヒントでも触れていましたが、大きいクッキーは小さいクッキーに比べ得点率が高くなっています。

多くの作品はここに注目し、大きいクッキーを優先して焼く、という戦略を取っていました。

高得点を出している作品では、さらに無駄な隙間を埋めるために、ビームサーチなどの探索を駆使する、特定のルールで評価値を算出し、評価値の高い状態を採用するなどのアプローチが取られていました。

他にも、壁沿いへの配置を優先したり、ステージ終了までに焼き終わらないクッキーを除外するなど、様々な工夫が見られました。

大きいクッキーと小さいクッキーの役割分担

今回の問題では「捨てる」という選択肢は問題に組み込まれていませんでした。

そのため、流れてきたクッキーは遅かれ早かれほぼ全て焼くことになり、「何枚焼いたか」が得点に直結することになります。

さらに前述の通り、大きいクッキーと小さいクッキーには明確に得点の差があり、高得点のためには大きいクッキーを優先して焼く必要があります。

そのため、最終的に「大きいクッキーを焼いた枚数を最大化」しつつ、その上で「小さいクッキーを焼いた枚数を最大化」していくことが高得点への鍵となっていました。

具体的なアプローチを見てみます。

まず大きいクッキーは得点率が高いので、これをできるだけたくさん敷き詰めるようにすると良さそうです。

次に、空いた隙間に小さいクッキーを詰めて得点を稼ぐということが考えられそうです。

しかし、「現在」だけを見て隙間を埋めてしまうと、後々焼き終わっていない小さいクッキーが邪魔をして大きいクッキーを置けなくなってしまう、ということが起きてしまいます。

ここで思うように点数が伸びない、あるいは逆に点数が下がってしまった、という方もいらっしゃったのではないでしょうか。

これを回避するために、小さいクッキーが大きいクッキーを邪魔しないように置いていくための工夫が必要になってきます。

3D の問題として捉える

既にお気づきの方もいらっしゃるかと思いますが、実はこの問題は、「焼き時間」を Z 軸とすることで3次元の充填問題として考えることができます。

各クッキーのスコアもこの3次元空間における体積を基準にしており、同じレーンのクッキーは単位体積あたりのスコアが均一になるよう設定されていました。

このことに気づくと、解き方をシンプルに考えられたり、既知のアルゴリズムを当てはめやすくなったりしたのではないでしょうか。

実際に投稿された作品の中にも、問題を 3D で捉えて解答している方もいらっしゃいました。

評価環境

評価環境で使われた乱数は、

でした。

今回は例年と違い、プログラムの各所で乱数の空回しを行っていました。

これは乱数の予測を難しくするための試みでした。

また、評価環境全体としてもビルドオプションの見直しや評価結果を見やすくする試みなど、参加者の方々が問題に集中できるよう改善を加えています。

まとめ

今回のプロコンは、開催期間が14日間と例年と比べて短いにも関わらず、昨年の3倍近い投稿数がありました。

乱数によって結果が変わりやすい問題だったこともあり、皆さん調整に余念が無かったのではないかと感じています。

開催中も抜きつ抜かれつの接戦が繰り広げられ、委員会一同、固唾をのんで見守っていました。

最終的には委員会の予想を上回る 270 万点台が叩き出されるという結果になり、参加者の方々の熱意と技量に驚かされました。

余談ですが、委員会の調べによると、開催期間中に焼かれたクッキーの総枚数は推定でおよそ... 2億枚以上！

一枚 10g だとすると重量にして 2000t、凄まじい量のクッキーが焼き上がりましたね。

最後になりますが、プロコン2018はお楽しみいただけましたでしょうか。

参加者のみなさんのおかげで、プロコン2018も大いに盛り上がりました。

熱のこもった作品をご応募いただき、本当にありがとうございました。