トヨタ自動車 実課題プログラミングコンテスト 2023 Spring に参加しました。
結果は優勝だー！やったぞー
以下解法です。（提出したサマリーとほぼ同一です）
コンテストページ
解法
最終提出コード
提出 #39889806 - トヨタ自動車 実課題プログラミングコンテスト 2023 Spring (atcoder.jp)
Bottom-Left 法と MCTS（Monte Carlo Tree Search）をベースとしたアルゴリズムです。
荷物の置き方を Bottom-Left 法のように(0,0,0)の点に向かって詰めて置くことにし、MCTS で置き場所/荷物の順番/荷物の回転を探索します。
方向の呼び名
メイン処理フロー
提出コード 3455 行目～3503 行目
得点計算式より、入力されたテストケースが収容可能かどうか、順番通りに詰め込めるかどうかを判断することが重要と考えました。
まず収容可能であると決め打って一定時間探索します。決め打つことでコンテナからはみ出るような選択肢を除外した探索ができます。もし一定時間で収容可能な解が見つからないなら、収容不可能と判断します。
収容可能な解が見つかった場合、順番通りに詰め込めると決め打って一定時間探索します。こちらも決め打つことで順番通りにならない選択肢を除外した探索ができます。もし一定時間で順番通りに詰め込める解が見つからないなら、順番通りに詰め込めないと判断します。
この判断結果により 3 つに分岐、それぞれの目的に合わせた探索を制限時間まで行います。
-
収容不可能 ⇒ はみ出る荷物の体積を減らす
-
収容可能＆順番通り詰め込めない ⇒ 荷物の順番前後数を減らす
-
収容可能＆順番通り詰め込める ⇒ MaxHeightを減らす
判断用の探索も目的別の探索もMCTSで行っており、評価値や選択肢等の部分的な違いしかないため、これらを5つ探索モードとして定義（提出コード3399行目）、探索中にモード変数を参照して処理を分岐させています。
判断後の目的別探索をしている際に、判断を覆すような解を見つけたらそれに合わせた分岐も行います。（例：収容不可能と判断し、はみ出る荷物の体積を減らす探索を行っていたら収容可能な解を見つけたので、順番通り詰め込めるかの判定処理に遷移する。）
最後に、見つかった配置を転倒数ができるだけ少なくなるように置く順番をソートします。（提出コード3507行目～3532行目）
荷物の置き場所候補
Bottom-Left法に倣い(0,0,0)の位置に向けて詰めるようにして置きます。
基本の置き場所候補
荷物を置いた際に左面、前面、下面が他のオブジェクトに接する場所が起き場所候補となります。オブジェクトには荷物だけでなく、コンテナの壁、コンテナの底、角の直方体ブロックを含みます。
置き場所候補は荷物の大きさ（種類×回転）によって変わります。
以下の図は上から下方向を見た状態を表していて、A,Bの荷物があるとき荷物Cを新たに置こうとしています。左右の図どちらも荷物A,Bの位置関係は同じ、荷物Cの座標も同じですが大きさが違います。左の図は正しい置き場所候補ですが、右の図は荷物Cの前面が他のオブジェクトに接していないため置き場所候補ではありません。
このように、場所は一緒でも配置する荷物の大きさによって起き場所候補かどうかが変わるため、座標＋サイズ下限という形で置き場所候補を表現しました。（提出コード2671行目PutPoint構造体のpoint_変数とlowerShape_変数）
探索時、荷物が置けるかどうかを判定するときにこのサイズ下限を使って判定します。
追加の置き場所候補1[真上に置く]
基本の置き場所候補だけでは困るケースがあります。
上記の図は前から奥方向を見た図です。荷物Aは上に物を置いてはならない荷物とします。
基本の置き場所候補だと、点Pと点Qが置き場所候補となります。点Qは荷物Aの幅を超えるというサイズ下限がついています。
点Pは荷物Aの上に物を置いてはいけないという条件から置くことができないので除外します。
上記左の図で、荷物Cを点Qに置けるかを考えると、サイズ下限を満たさないため置くことができません。上記右の図では、荷物Dを点Qに置けるかを考えると、サイズ下限は満たしますが、接地面積6割の条件を満たせないため置くことができません。
これらのようなケースがあるため、配置済みの荷物の真上も置き場所候補としました。
以下の図のように、荷物Bの上の点Rであれば、荷物CもDも置くことができます。
追加の置き場所候補2[接地面積ぎりぎり6割]
前述した真上に置くケースで、接地面積6割ぎりぎりの位置に置いたほうが残った空間を広くできます。
上記図のように、荷物C、DについてX軸方向にずらした時に接地面積ぎりぎり6割を満たせる位置S、Tも候補とします。同様にＹ軸方向にずらした時に接地面積ぎりぎり6割を満たせる位置も候補とします。（斜め方向も試しましたがスコアが悪化したため採用しませんでした。）
この置き場所候補は、荷物の種類×回転6種×2方向（X軸方向とＹ軸方向）分あり、数が多いです。数が多いことによる処理速度低下の問題があったため、荷物と方向につき回転は一番原点に近い場所になる1種に限定しました。
計算箇所
状態を表すデータ
提出コード2734行目のState構造体が荷物の配置状態を表し、置き場所候補も保持しています。
追加の置き場所候補
提出コード2998行目のAddItem関数で荷物の追加と置き場所候補の更新処理を行います。
提出コード3024行目～3128行目で基本の置き場所候補を計算しています。
新規に追加する荷物1個と既存のオブジェクト2個を総当たりし、新規追加される置き場所候補を計算します。ここが本アルゴリズムにおける処理時間のボトルネックであるため、高速化が重要です。
提出コード3168行目が真上に置く候補の追加。
提出コード3171行目～3258行目で接地面積ぎりぎりの置き場所候補を計算しています。
置き場所候補のマージ
提出コード2808行目のPushPutPoint関数で、既存の置き場所候補と新規置き場所候補のマージ、置き場所候補のソート、無効になった置き場所の削除、をまとめて行います。
置き場所候補のソートは探索時に置き場所の座標をXZYの優先度でソートしたものとYZXの優先度でソートしたものが必要なのでここで準備します。
既存の置き場所候補はソート済みであるため、新規置き場所候補をC++標準関数でソート、あとはソート済みリスト同士のマージとなるためマージソートのように処理します。
マージ中に、座標は同じでもサイズ下限が違うケースが出てきます。これを別な要素とするとデータ数が増えて速度低下につながるため、サイズ下限を両方の最小値にして1つにマージするようにしました。（提出コード2905行目～2916行目）
これにより置き場所としては不正（左面、前面、下面が他のオブジェクトに接しない）な候補となりえますが、探索時の走査順的にこれが採用されることはほぼないのとスコア的にも問題なかったのでこのようにしました。
探索
提出コード3537行目～3748行目
MCTSアルゴリズムによる探索を行います。
展開処理の候補手
提出コード3750行目TryNewNext関数
体積大きい順、回転後の高さが低い順（＝底面積大きい順）に、置き場所候補XZY順で最初に見つけた配置可能場所と、置き場所候補YZX順で最初に見つけた配置可能場所を候補手とします。
荷物の種類×回転ごとに2つが候補手となりますが、以下の探索モードでは4つの候補手になります。
- はみ出る荷物の体積を減らすモード
はみ出る候補手とはみ出ない候補手両方を追加します。 - 荷物の順番前後数を減らすモード
順番前後する候補手と順番前後しない候補手両方を追加します。
各ノードの子ノード数には上限を設けます。そのため優先度の低い候補手は探索されません。
プレイアウト時の候補手
提出コード3933行目Playout関数
まだ置いていない荷物の中で一番体積が大きい荷物を置くことにします。XZY順とYZX順どちらにするかをランダムで決めます。置き場所候補を順に走査、各置き場所候補について回転をランダムな順番で試し、最初に見つかった場所と回転で配置します。これをすべての荷物を置くまで繰り返します。
残っている荷物のうち一番体積が大きい荷物を置けなかった時点で解が見つからなかった扱いにするのが良いようで、次の体積の荷物を置くのも試しましたがスコアは悪くなりました。
置き場所候補の2つの順序
置き場所候補をXZY順とYZX順の2つの順序で走査し両方を候補手としている理由ですが、XZY順のみだと最初に置く荷物は必ず(0,B,0)になります。すると最初に置いた荷物が邪魔でそれ以降の荷物を(B,0,0)に置くことができません。テストケースによっては(0,B,0)よりも(B,0,0)に置いたほうが良いケースがあったためYZX順を追加しました。
最初の置き場所の問題のために追加した順序ですが、それ以外の場所でも良い選択肢になっているようで、最初に限らず常にこの順序も使うようにしました。
スコア更新の見込みのないノードの枝刈り
荷物を1個配置するたびにペナルティが増えていくようなスコア設定になっているため、見つかっているベスト解よりもペナルティが増えた時点でそれ以降の探索は無駄とわかります。
提出コード3281行目CanPutBest関数にて、配置可能かの判定とベストスコア更新の見込みがあるかどうかも判定しています。提出コード4127行目～4146行目のIsNoChance関数でも更新見込み判定を行っています。
判定の際に簡易的な転倒数（変数名easyInversion）を使って判定している箇所があります。簡易的な転倒数は荷物の上下の位置関係により転倒数を増やしてしまうペアの個数です。実際の転倒数はこれ以上になります。転倒数計算が重かったため用意したものですが、最終的に転倒数計算が高速化されたため不要だったかもしれません。
その他工夫点
ノードに状態を持たせない
ノードに状態を持たせず、ノードをたどりながら状態を計算していくことでメモリ使用量を減らしています。おそらくその分パフォーマンスは落ちていますが、メモリ制限に引っかかる可能性があったためこのようにしました。
ノード選択指標
ノードを選択する際の指標は[UCB1-Tuned]を使用します。これはよくMCTSの説明で使われる[UCB1]よりも性能が良いとされています。実際にUCB1よりもスコアが良かったので採用しました。（提出コード2656行目～）
ベスト解まで展開
探索を始めるときとベスト解を見つけたとき、ベスト解のノードまでノードを展開します。
これによりベスト解に近い選択肢が選ばれやすくなることを期待して入れましたが、それほどスコアに寄与していないようです。（提出コード3547行目～3579行目、3610行目～3655行目）
メモリプール
ノードの展開に際して動的にノードを追加していくことになりますが、動的メモリ確保は時間がかかります。あらかじめ大容量のメモリを確保しておき、その領域から必要な分を少しずつ取ってきて使うことで、動的メモリ確保の回数を減らし高速化しました。
置く順番ソート
できるだけ転倒数が少なくなるようにソートします。
2つの方法を用意しました。どちらも最適解を出す解法ではありません。両方試して転倒数が少ない方の結果を使用します。（スコア計算式的に転倒数の重要度は高くないと考えたため、あまり検討していません。）
方法その1
提出コード2226行目SortedNew関数
荷物を順番通りに置いていきますが、上下関係により依存する（＝先に置かなければならない）荷物があるならそれらを置いてから置きます。
もし同じ種類の荷物で、他の荷物に依存する荷物が複数あるなら依存数が少ないほうから選んでいきます。例えば同一種類の荷物AとBがあり、Aは3つの荷物に依存、Bは2個の荷物に依存しているとします。この場合は荷物Bのほうが依存する荷物が少ないためBの荷物を先に置きます。
依存する荷物を先に置く際も、荷物を順番通りに置いていき、依存するものを先に置くということを行うので再帰的な処理になります。
方法その2
提出コード2189行目SortedOld関数
トポロジカルソートの要領で行います。置ける状態になっている荷物のうち一番種類番号が小さいものを置くということを繰り返します。
bit演算による高速化
大抵のケースでは荷物の個数が64個以下であるため、64bit変数を使ったbit演算で高速化を行っています。一応64個を超えるケースも存在するため、方法その1のbit演算を使用しない版も用意してあります。（提出コード2464行目SortedIndexOver64関数）
解法は以上です。
感想等
コンテスト序盤は先行研究があると思っていろいろ調べていた。
シーケンスペアとかシーケンストリプルとかいうのを見つけて、これなら焼きなましできるやったぜと思って実装してみたら、スコアが伸びず単純なBottom-Left法にも負けていた。今回の問題設定だとおそらくうまくいかないことがわかってきて方針を変えた。（角の長方形オブジェクトと接地面積6割あたりが原因）
Bottom-Left法は単純すぎてあんまり使えるとは思ってなかったけど、いろいろ試した中では一番スコアが良くて、これをベースにちょっとランダムに散らすのを考えた。さらに、良い解が出た場合は途中の状態も良い状態になっていて、途中からまたランダムに散らすようにすればいいのではと思い、これってMCTSでは？ってなって実装してみたら良いスコアが出て方針が固まった。
高さを制限してその制限に収まるかどうかを判定、みたいな2分探索的な解法を思いついて、それが5つのモード遷移という形になった。制限時間が決まっているのでその中で時間を区切って判断したけど、実務で使う場合はそれぞれ決め打ちして3回実行すれば良さそう。（これサマリーに書けば良かったな）
スコアがぶれやすい（条件を満たすかどうかでスコアが大きく変動する）ので、修正が良いものかどうかの判断が難しかった。ローカルでは1000件でテストしていたけどそれでも足りなかった気がする。毎回ベスト解が出ているような簡単なケースは除外して難しいケースを増やすと良かったかもしれない。
サマリー賞があるということで、頑張って書いてみたけどなかなかうまい表現ができなくて悩んだ。期限もあるし疲れたしで力尽きた。AIにお願いしたらうまいことやってくれるのかな。
コンテスト2週間＋サマリー1週間でトータル3週間の長い戦いでした。やっと休めるよ……
