考察

• 2次元のオーブンに焼き時間を考えて生地を詰める代わりに、時間軸を3つ目の次元として「20×20×1000のオーブン」に「時間軸方向に必要な焼き時間だけ膨らませた直方体の生地」を詰めることを考えればよいことが分かります。
• 各レーンについて、使わなかった生地は結局手元に残るため、スコアを伸ばすためには「スコアを気にせず1枚でも多くのクッキーを焼く」ことが重要になります。さらに、クッキーを焼く枚数を最大化するためには、3次元空間内の生地の充填率を最大化すればよいことが分かります。
• 大きい生地の得点が小さい生地の得点より大幅に高いので、まず大きい生地を配置し、隙間に小さい生地を詰めるとよさそうであることが分かります。

方針

2次元の箱詰め問題を解くアルゴリズムであるBottom-Left法を3次元に拡張したものをベースに、配置順の探索を行いました。各生地は、配置可能な座標 (x, y, z) のうちで、(z, y, x) が辞書順で最小となるような場所に順番に配置されます。途中で未知の生地が補充されるため遠い未来ほど不確かになるので、考えられる順列のうち最初の4手～5手に限って全探索を行い、残りは与えられた順番のまま配置しました。

最初に大きい生地についての最適な順列を決定し、その後で小さい生地についての最適な順列を決定しています。これにより、大きい生地を優先的に配置しつつ全体の計算量を減らすことができます。また、細かいパラメータ変動によるスコア上昇狙いが大きい生地と小さい生地の2段階に分けて実行できるという利点もあります。

高速化

探索を多数行うため、生地の配置の高速化は非常に重要になります。配置済みの全生地に関して判定を行う必要がありますが、これを空間上の全点に対して実行するとタイムオーバーします。そこで、

• z値が小さい方から順に調べていく
• あるz値に生地を置いたときに交差する可能性のある配置済みの生地を全て取り出す
• それらをz方向に射影して2次元上での問題に帰着させる

という方法を取ります。さらに、新しく置かれた生地は「必ずどこかの生地の天面に接している」ため、探索が必要なz値は高々 (配置済みの生地の個数)×2 種類になります。しかし、これでも2次元の問題に対して 20×20 通りの配置場所を調べていると時間がかかるので、ビット演算を使った高速化を考えます（文字だけだと伝わり辛いと思うので、ソースコードを見ながら読んでみることをお勧めします）。

20×20のマス目の交点（および四隅）を考えます。すると21×21になります（今考えると、元々端には置けないため21×21にする必要はなかったかもしれません）。これらすべての点に対し、「生地の左上」がその点に重なるように配置可能なら0、配置不可能なら1が書き込まれているような2次元のビットボードを考えます。このビットボード上のビットに、左上を0番目として、横書きの文字を折り返すように番号を付けます。すると、最も若い番号の0が書き込まれたビットが生地を配置する位置になります（左上を原点、右をx正、下をy正方向と考えてください）。このビットの検出は、popcountと呼ばれるビット演算により高速に行うことができます。CPUがサポートしている整数演算は基本的に64ビットまでであるため、1つの long long 型に3列分のデータを格納させ、7要素の配列を使うことで21×21のビットボードを表現しました。

後はどのようにしてこのようなビットボードを作るかですが、置こうとしている生地・置いてある生地が共に長方形であることより「ビットボードに含まれる長方形内部を塗りつぶす関数」が作成できればよいことが分かります。この関数もビット演算を用いて作成できます。

• シフト演算と減算により、「長方形のx方向への射影」「長方形のy方向への射影」を表すビット列を作成します
• x方向への射影を3列分に（21ビットずつずらして）コピーします
• ビットボードを表す配列の各要素にOR演算で書きこんでいきます。ただし、y方向への射影を見ながら（余分な列に書き込まないように）マスクを適宜行います。

ビットボードに書き込む際のマスクの種類は2の3乗で高々8通りなので、予め定数として定義しておきます。これで高速に生地の配置可能な点を求めることができました。

配置の評価

先が見えないオンライン問題であるため、非常に苦労しました。最終的には、考察を踏まえ次のような評価関数を採用しました。

• 評価するz値の最大値を決める
• 0～最大値までのz方向の区間を適当に分割し、0に近い区間が重要視されるように重みを設定する
• 各区間に対して、交差している生地の体積の総和を求め、全ての区間に対する重み付き総和を評価値とする

また、各ステージの終盤では代わりに次のような評価関数を採用しました。これは、終盤に限っては（使わないピースを「選別」できるため）単にスコアが最大化されるような評価関数が有利であると考えたためです。

• 1000ターン目までに焼きあがる全ての生地のスコアの総和を評価値とする

その他

その他の細かい工夫点はソースコード内のコメントをご覧ください。