トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）参加記
トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）に参加して優勝しましたー
自分の解法を解説します。
問題
複数のクレーンを操作して、すべてのコンテナをできるだけ早く搬出しよう。
詳細は問題ページを見てください。
初めに
問題文では「コンテナ」となっていますが、ここでは「箱」と表記します。
基本方針
- 一時置き回数を最小化するような搬入順序をDPで求める
- クレーンの移動経路は縦x横x時間の3次元グリッド上でBFSの要領で求める
- タスクをクレーンに割り当てる問題と考え、割り当て方をビームサーチで探索
これらの方針は公式解説でされているものと同じです。
すごくわかりやすく解説されていますので、先に公式解説を見ることをお勧めします。
本記事では、公式解説で話されていない内容を中心に書きます。
重複状態の除去
タスクを割り当て方を決めるビームサーチでは、割り当ての順序が違っても結果的に同じ割り当てになるケースがあります。
例えば、タスクAとタスクB、クレーン1とクレーン2があるとき
・タスクAをクレーン1に割り当て、次にタスクBをクレーン2に割り当てる
・タスクBをクレーン2に割り当て、次にタスクAをクレーン1に割り当てる
これらは順序は違えどクレーンに割り当たったタスクは同じです。
違うのは経路で、先に割り当てたクレーンが先に動き、後に割り当てたクレーンは先のクレーンを避けた経路になります。避けるなどの無駄な移動が発生した場合はタスク完了にかかるターン数が伸びているので評価値が悪くなります。
この場合は同じ状態とみなして、評価値が悪いほうは見込みがないものとして捨ててしまいます。
同じ状態と判定する方法は、クレーンの位置と各番号の箱がどこに置いてあるかでZobristHash化して、ハッシュ値の一致で重複と判定しました。
ハッシュ化する際に、大クレーンと小クレーンは区別する必要がありますが、小クレーン同士は位置関係が変わっても同じなので区別しないようにします。
高速な経路探索
今回の問題は5x5と盤面が小さいので、ビットボードが使えます。
以下のように各セルに番号を振ります。
32bitの変数1個で各場所にクレーンがあるかなどを表現できます。
例えば、2と13の位置にクレーンがいる状態は2bit目と13bit目（0-indexed）が1でそれ以外のbitが0として表せます。
クレーンの位置がビットボードに記録されているとき、ビットボードを右に1bitシフトすると、クレーンの位置が左に1マス動いたことになります。右に6bitシフトすると上に1マス動いたことになります。同様に左に1bitシフトは右に1マス、左に6bitシフトは下に1マス動いたことになります。
グリッドの左端の例えば12の位置にいるときに、左に1マス移動である1bit右シフトをすると11になります。このような不正な移動を除外するためにダミー列を追加しています。
これらの性質を使うと、経路探索時の「あるターンに到着可能な場所から、次のターンの到着可能な場所を求める」部分がビット演算で高速に計算できます。
以下はある場所から目的地に着くまでの最短ターンを計算するサンプルコードです。
このサンプルコードではクレーンのすれ違いを考慮していません。少し工夫すれば対応できます。
経路の復元は、目的地に到着するターンを計算するときに出た、各ターンの到着可能な場所ビットボードをとっておいて、目的地側から前のターンにどこにいたかを遡るようにして辿れば復元できます。
一時置き回数が最小でない順序も許容する
一時置き回数最小の搬入順序だと、同じ行からの搬入が続いたときにいくつかのクレーンが待たされてしまうことがあります。待たされるぐらいなら一時的に置いてもよいので少しでも搬出口に近づくように運んでおいた方が、トータルのターン数は減らせるというケースがあるようです。（他の理由もあるかもしれません）
例えばseed=38は一時置き回数0が達成できます。一時置きを禁止すると65ターンかかり、一時置きを許容すると3回の一時置きをして60ターンで済みました。
許容するといっても一時置き回数が多いこと自体はやはりロスになるので、最適解の順序からあまり離れすぎないように制限しました。
評価値
以下を評価値として使いました。
・搬入した箱の総数
・行ごとの搬入数
・搬出した箱の総数
・行ごとの搬出数
・一時置きされている箱の場所（一時置き場所候補3x5=15セルそれぞれで違う重み）
・クレーンごとのタスクが完了するターン数
・全クレーンのタスクが完了するターン数
・箱を拾いに行くときのターン数のロス（マンハッタン距離との差）
・箱を運ぶときのターン数のロス（マンハッタン距離との差）
・一時置きした回数
・一時置き最小回数の搬入手順からどれだけ外れたか
・拾うための移動にかかった総ターン数
・運ぶための移動にかかった総ターン数
評価値調整法
あまりお勧めできる方法ではありませんが、自分のやってる評価値調整法を書いてみます。
・評価値として使えそうなものを出します。
・大きいほうがいいのか小さいほうがいいのかで符号を決めます。
・線形なのか指数なのかなど、関数の形を決めます。
・評価値に重みを付けて足し込みます（ものによっては掛けたり割ったりも）
・たくさんのテストケースを回してみて、スコアが上がるように重みを手動調整します。
・スコアが上がりそうなら採用。下がるなら不採用。怪しいならOptunaでちょっと調整して判断。
・こんな感じでどんどん追加していきます。
・コンテスト終盤にOptunaでまとめて調整します。
理詰めで考えるのは苦手なので、とにかくいろんなことを試すように心がけています。
枝刈り
高速化や不要な割り当てを防ぐために、タスク割り当てに次の条件を課しました。
・搬出可能な箱は一時置きしない
・各箱につき一時置きは1回まで
・一時置き場所、現在の置き場所よりも搬出口に近づかなければならない
・5行のうち1行は中心3列に箱を1つも置かない
・タスク完了ターンが最大のクレーンには割り当てない
・タスク完了ターン最小のクレーンのターン数よりも、そのクレーンのタスク完了ターン数が一定以上大きければそのクレーンに割り当てない
・タスク完了までの最短ターン（マンハッタン距離で算出）よりもが一定以上遅れるなら割り当てない
ビジュアライザ
seed=0 Score=66
感想など
・時間を含めた3次元上で経路探索することを思いついて、これすごい発見だと思ったのですが結構みんな思いついてそうですね……アルゴりょくぅ？
・これだという解法に早めにたどり着けたのが良かったです。そのぶん高速化とパラメータ調整に時間をかけることができました。でも最終日は何試してもスコアが上がらず苦しかったです。
・固定長配列大スキーなので入力サイズ固定なのはうれしい！ビットボードも使えてうれしい！
以上、ありがとうございましたー
