※画像は公式Visualizerよりお借りしています。
はじめに
この記事は2023/03/05 - 2023/03/19にAtCoderで行われました実務解決型のコンテスト「トヨタ自動車 実課題プログラミングコンテスト 2023 Spring」の解法を紹介するものになります。
3/5から3/19の二週間、トヨタ自動車 実課題プログラミングコンテスト（以下実課題コンテスト）に取り組みました。Visualizerが3Dなうえに、荷物しきつめ問題のプログラムは一度書いてみたかったので終始楽しみながら取り組むことができました！
まだシステスは行われていませんが暫定2位ですシステス後も2位でした。
ところどころ間違っているかもしれません。間違いを発見されましたら優しく教えていただけるとありがたいです。
問題の概要
こちらは問題文を見ていただいたほうが早いと思われるので割愛します。簡単に言えば「コンテナ内に直方体の荷物を積み込む」という問題です。
問題文はこちら
ここで用いる独自の表現
（荷物の）依存関係
私のプログラムでは、山登りの際にどの順に荷物を積むかは確定させず、荷物の配置だけを考えます。しかし、その配置計画を採用して実際に積む際には、荷物の配置によって「この荷物を先に置かないとあの荷物は置けない」という縛りが発生します（わかりやすいのは「あの荷物はこの荷物の上に載っている」という配置）。この、配置計画における荷物同士の順序の縛りを依存関係と呼びます。
最終提出の解法
以下、最終提出の概要です。
言語:go言語
これはただの好みです。goの並行処理で100ケース試すものを作ったり、今回は実行時間を気にするタイプの解法だったのでgoのpprofでプロファイリングしたりとそれなりに利点はありました。
解法:乱択+部分破壊による山登り法
以下はTwitterで行った解法ツイートです。
#TOYOTAHC2023SPRING
— MON.T+α (@montplusa) 2023年3月19日
実課題コン 暫定2位
ざっくりとした解法
乱択で荷物積み上げ -> 一部の荷物とその荷物の上にある荷物を破壊
を時間いっぱいやる
（制限時間0.6秒くらいで時間内に三回解いて、一番うまくいったものを出力します）
もう少し詳細を確認していきます。
乱択で荷物を積み上げ
まずはランダムに荷物を積んでいきます。荷物の配置を決める順ですが、このフェーズが来る度に
・底面積の大きい順
・完全ランダム順
のどちらかを採用します。
荷物を積む際はすでに配置の決まった荷物の角（と四隅の角）と荷物の回転方向をランダムに選択します。そして、その角に対して下の図のように四方向からくっつけてみます。
ケースによりますが、これらの設置の仕方は高確率で不正な設置になるため、不正でない設置が見つかるまで再挑戦します。ある程度再挑戦しても見つからない場合は候補手なしとみなしてこの積み上げフェーズを終了します（速さを優先したために実は有効手が存在しても少ない場合は見つける前に終了します）。
積み上げの際には、これまでにしてきた最善の積み上げ結果を上回るようなペナルティを受けてしまうようなものは不正な設置とみなします（過激派）。これによりこれまでの積み上げよりも悪い積み上げを長々としてしまう可能性を防ぐことができます。
ペナルティの計算について、正確な順序ペナルティを計算する際には積む順番を確定させる必要がありますが、この段階では順番を確定させていないため厳密な値とは違う値で計算しています。 最善の配置を見つける段階では「各荷物はその上に載っている荷物やさらにその上に載っている荷物よりも先に置かなければいけない」というのを利用し、その依存関係において荷物の種類番号が逆転していないかを確認します。逆転している場合は荷物の種類番号の差を仮転倒数として追加します。これは荷物の種類番号が近い場合（特に連続している場合）にはこれによる転倒数は1で済みますが、種類番号が離れている場合には他の場所でも順序入れ替えが発生したときに大幅に増加する恐れがあるからです。順序最適化についてはまた別の部分で紹介します。
上で述べたペナルティですが、はじめのうちは順序ペナルティを一切許容せずにやっていきます。順序ペナルティありである程度の解ができてしまうと順序ペナルティなしの状態への遷移が難しくなってしまうのが理由です。
配置計画を評価
乱択で配置計画ができた(or途中で候補が見つからず打ち切った)ら、配置計画を評価するフェーズになります。基本はペナルティ（順序関係については上述）をもとに評価しますが、荷物がコンテナをオーバーしている場合には追加の評価基準が与えられます。この追加基準はコンテストのスコアに基づく評価ではなく、山登りにおいて登りやすくするための評価であり、解が改善しにくそうな状態に減点が入ります。
より具体的には以下の要素がおよそ同じくらいの影響力になるように設定しています。
・x,yがそれぞれ0付近のエリアにおいて隙間がないか（これによりx=0,y=0側のコンテナの壁は比較的しっかりと埋まる）
・荷物が高いところにないか（下が密、上が疎になっているほうが破壊→積み上げをした際に改善させやすい）
・コンテナ内の荷物の表面積が大きくないか（荷物同士がくっつくと無駄がないので改善させやすい）
この評価がこれまでのもっともよい評価を超えていたらこれを最善の配置計画として更新します。
部分的に破壊
最善の配置計画を部分的に破壊します。
まずオーバーしている荷物は問答無用で破壊します。転倒数0での収容に成功していて高さ勝負となっている場合は一番高い荷物も破壊します。
その後の破壊方法は3つあります。いずれも、対象のものを破壊したのちにその荷物の上に載っていた荷物を順次破壊します。
・（収容成功した場合に限り）荷物の依存関係で順序関係が入れ替わっているものをランダム選択し、どこかにねじ込む。その際めり込んだものを破壊
・ある程度の隙間ができてしまっているところを探す。その付近に直方体エリアを設定してエリア内の荷物を破壊
・各荷物を確率pで破壊
一つ目は転倒数最適化において効果を発揮する破壊方法なので、まだコンテナを超えている段階や、転倒数0が達成された場合には使われません。
破壊活動が終わったところで、再び乱択フェーズに入ります。
破壊の様子
最善の計画を行動として出力
約0.6秒制限で3回上記の山登りを行います。その中でもっともよかったものを行動として出力するわけですが、ここにきて初めて荷物の積み込み順を考える必要があります。
まずは、貪欲に順序を決めます。貪欲の方法ですが、「上に荷物がのっていない荷物で種類番号が最も大きいものを選び、取り除く」を荷物がなくなるまで繰り返します。そしてこの順を逆順にすることで貪欲な積み込み順が完成します。
続いて順序をswapして最適な順序を求めます。ランダムに荷物を一つ選び、荷物の積み込み順を今の順番より後のどこかに設定します。この荷物と依存関係にある荷物はそれに合わせて移動したりします。（うまく伝えられないので下の例を見てください）
例：
荷物5の上に荷物6、さらにその上に荷物3があるとし、それ以外の荷物は離れ離れに置いてあるとします。また、設置順として1,2,5,6,3,4,7,8,9というものが貪欲で得られたとします。
このとき、荷物5の順序を2つ後ろに設定するというのはこのような遷移を表します。
荷物3や6は5と依存関係があるのでswapはできず後ろに続いていきます。
仮に荷物7が荷物5の上に載っている場合は次のような遷移になります。
転倒数の変化は途中の過程を追うことで求まるので、「ランダムで選んだ荷物に対しいくつ後ろに下げるのが最もよいかを求める」を繰り返すことにより短い時間で（ほぼ）最適を得ることができます。
おわりに
ここまで読んでくださった方、ありがとうございました。この頃はコンテストに出るたびに自分が少しずつ成長できているのを実感できてうれしいです。
Visualizerが3Dなのには驚いたとともに、自分のプログラムが荷物を積み込んでくれる様子がとても感動的でした（「えっそこ入るのに・・・」みたいなもどかしさもしばしばありましたが）。巷では次のヒューリスティックコンテストが始まっているとか。さすがにしばらくは体を休めて、落ち着いたらそちらのコンテストも見てみようかなあなどと考えています。改めて、このコンテストの開催に携わっていた方々、他の参加者の方々、楽しい時間をありがとうございました！
おまけ
以下は解法の補足情報を雑多に書いたものです。
・有効手の計算を行っていないために、一つの荷物を設置するために数十～数百回も設置を試みなければいけない。そのため、かなりの高速化が必要だった。
・有効手の計算を行わないことによる他の欠点として、合法手が作りにくいケース（上に荷物を載せられないもの・底面変更不可の大きなものがあるケース）では、山登りに十分な試行回数が確保できていないという点があった。
・「確率pで破壊」がほぼ全破壊の可能性もあるので十分な時間があれば必ず大域解に到達できるのだが2秒（0.6秒）ではケースによってほぼ無理だったり。山を登りきれていない印象が強かった。
・「順序入れ替えありなら収容できる」というケースは想像以上に少ない(seed0~99だと10ケースもなかったと思う)上に、頑張って収容させた結果転倒数勝負でほとんど相対スコアがもらえない可能性も高いので、まずは順序入れかえなしで血眼になって探すのがスコア的には良さそうだった。3回に分けたのも局所的なところに陥って順序入れ替えなしの解を逃すことが減るようにだったりする。代わりに時間が足りず収容できるとこまで登れなかったりするのでここはトレードオフ。
以下はコンテスト中・後に思ったことを雑多に書いたものです。
・言及可コンテストだったので最初の解法くらいは共有したいなあと思ったけど最後まで解法を変えなさそうだったので控えた
・中盤以降は新しいアイデアもなかったので高速化に躍起になっていたが、終盤で「速度を多少失ってでも一回一回で出て来る解をまともにしたほうが良いのでは」となり微改善した
・焼きなまし、optuna使いたいけどどちらも全く使えなかった。使い方が下手なのかもしれない。
・今回ローカルでの実行を並行処理にできたのは革新的だったが、コア数を上回らないように制限しているにもかかわらずパフォーマンスが安定しなかった。
・Visualizerは作れなかった。どちらかというとスコアやデバッグ情報とにらめっこする時間が多かった。
・実課題なのに「荷物を破壊」とか「ねじ込む」とかいう表現してごめんなさい
・プログラム中の構造体の名前がいつもの癖でGameStateとかActionとかになってる
・Goは十分速い言語だと思っているので言語の実行速度は言い訳にできないんだよなあ・・・
・コンテスト後半は微改善しつつ順位表で上振れを引いて相手を絶望させる戦術をとっていたんですが、逆に火をつけてしまったかその上振れさえも超えられてしまいました・・・
・bottom-left法・・・。知識不足でした。調べてきます
・複数コンテストの取り組み方の最適化に失敗。逆にAtCoderのヒューリスティックコンテスト開催日時をユーザーの満足度について最適化してもらったほうがいいのでは？
・どうやら0.6秒制限の試行のうち一回でもvalidな解の形成に失敗してしまうと、積むことのできた荷物まででペナルティ計算してしまい採用してしまうっぽい。多分システスの2WAはこれ。
