#AHC033 参加記(暫定209位)

AHC033お疲れ様でした。暫定209位でした。
スコアを伸ばせそうにないアプローチに入り込んでしまった割には、それなりの順位が出て満足しています。
今回はそんなにいろいろやってはないですが、考えていたことはあったので、整理の目的もかねて参加記を残しておきます。

問題

• $5*5$のマスがあり、左側からコンテナが搬入され、クレーンを使ってコンテナを移動させ、右側から搬出する
• 一番右側の列は搬出用の出口で、コンテナを置いた瞬間即座にその列から搬出される
• 一番左側の列は搬入口で、マス上にコンテナもクレーンもなければ搬入待ちの先頭のコンテナが置かれる
• クレーンは全部で5台ある
  • 複数のクレーンが同一のマスに存在することはできない
  • クレーンはコンテナを掴んでいなければ、他のコンテナが置いてあるマスを自由に通過できる
  • クレーンのうち1台だけは大きなクレーンで、大きなクレーンに限り、コンテナを掴んでいる状態で他のコンテナが置かれているマスを通過できる
• クレーンは各ターンに以下の行動を選択できる
  • 移動 上下左右の隣接マスに移動できる
  • 掴む コンテナを掴んでいない状態で、クレーンが今いる場所にコンテナがあれば、そのコンテナを掴むことができる
  • 放す クレーンがコンテナを掴んでいる状態で、今いるマスに他のコンテナが存在しなければ、そのマスに掴んでいるコンテナを下すことができる
  • 待機 何もせずにその場にとどまる
  • 爆破 コンテナを掴んでいない場合に選択可能で、以降そのクレーンを存在しないものとして扱うことができる(爆破して以降は、そのクレーンが最後にいた場所を他のクレーンも通ることができる)
• 以下の3ステップを1ターンとする
  • 搬入
  • クレーンの操作
  • 搬出
• 操作は$10,000$ターンまで行うことができる

目的

• できるだけ短いターン数で、コンテナを正しい搬出口から正しい順番で搬出せよ。
  *より形式的には、以下の式で定まるコストができるだけ小さくなるようなクレーンの操作列を求めよ。

       \begin{align}
       M_0 + 100*M_1 + 10000*M_2 + 1000000*M_3.
       \end{align}

ここで、

• $M_0$ かかったターン数
• $M_3$ 搬出されなかったコンテナ数
• $M_2$ 搬出したコンテナのうち、誤った搬出口から搬出したコンテナの数。ここでコンテナ番号$n$のコンテナの正しい搬出口は、$n/5$の整数部分行目の搬出口である。¹
• $M_1$ 正しい搬出口から搬出したコンテナについての転倒数の総和
  である。

正の得点を得る (5日目)

今回は最初の週末に沖縄へ行くとっても大事な用事があったため、参戦は週明けからでした。
まずは正の得点を得ます。といっても、今回は誤った操作をしてWAなんてことにならなければ得点はいつでも正なので、これは簡単です。
すぐに思いつくものとして、とりあえずひたすら左右に動いて何も考えずに搬出するコードを提出します。
絶対スコアは$10,007,200$点。同じ点数の人がたくさん順位表に並んでいました。
seed=0 200,246点

とりあえず搬出列を正しくする

ひとまず搬出は終わらせましたが、コストの計算式を見る限り、正しい搬出口から出すだけでもめっちゃ嬉しくなれそうです。搬出の順番まで考えようとすると、大きいコンテナを一時的に避けておいて……そうするとクレーンが通れるマスが減ってしまって……と考えることが増えますが、ひとまず正しい列から搬出するだけなら逐一処理すればそんなに大変ではないでしょう。
先ほど提出した左右にただ移動するだけのソースコードをベースにしつつ、今持っているコンテナについて搬出すべき正しい列を計算してあげて、クレーンを上下に移動させて列を合わせながら横に移動していくコードにしました。
他のクレーンが移動したい先を既に占有していれば1ターン待ってみたりしています。
絶対スコアは$90,166,653$点。先ほどよりも増えてしまいました。実装にバグがあって、クレーンがぶつかってしまっているようなケースがありそうです。素直に一つずつクレーンを動かせばよかったのですが、それをサボった結果うまくクレーンが動いてくれないケースがありそうです。それはそうと、うまく動く事例ではスコアが改善しています。狙いは正しそうです。
seed=0 3,567点

スコアの考察

ひとまず簡単に実装できそうな正しい搬出口から搬出するコードを書いてみました(それでもバグっていますが)が、それでも順位表を見るとかなり低い印象があり、まだまだ改善できそうです。ここでスコアの計算式を改めて見直してみます。AHCではあんまり気にしなくていいスコアのペナルティと、気を付けないと話にならないペナルティがあることがこれまでの経験からわかってきています。今回でいえば、スコアの計算には4つの変数が影響しますが、これらの係数はそれぞれ100倍の差があります。具体的にいえば、100ターン無駄な動きをすることの罪と、搬出したコンテナの転倒数が1増えることの罪が同じ価値ですし、転倒数の総和が100増えることの罪と、誤った搬出口からコンテナを一つ搬出することの罪が同じだけの価値を持ちます。問題文には最終的な目的として、できるだけ少ないターン数で…と記載がありますが、そもそも正しい順序で搬出することを確実に行わないと、スタートラインにすらたどり着けなさそうです。
今回のコスト計算でいえば、たとえ転倒数を1減らすのにめちゃくちゃターンを使うようなルールしか思いつかなかったとしても、それが100ターン未満なら採用すべきです。冷静に考えて、盤面の広さからしても転倒数を1減らすのに100ターンもかかるとは考えられないので、まずは転倒数を0にすることに注力すべきでしょう。
とはいえ、転倒数を0にするための改修でコードにバグを埋め込んでしまい、そもそも搬出が完了できないままWAになるようでは意味がありませんし、あるいは無限ループが発生して10000ターンまで何もできないようなものにも意味がありません。転倒数を0にしつつ、確実に終了するようにする、きっちり考えないといけなさそうです。

クレーンを同時に動かすことをやめ、転倒数を0にする（6日目）

上述の通り、クレーン同士がぶつかるような非合法手を採用してしまうことや、無限ループに陥るようなことはできるだけ避けたいです。そこで、一旦クレーンを同時に動かすのをやめて、一つずつ動かしてみることにします。これで転倒数を0にするコードを提出してみてから、次の戦略を考えることにします。
クレーン同士がぶつかってしまう問題について、いくつか考察をして、実装戦略を考えてみました。まず、小クレーンはコンテナを掴んでいるとき、他のコンテナのあるマスを通れません。逆に言うと、することがないクレーンはコンテナの上に放置しておけば、少なくとも小クレーンについてはそのクレーンとぶつかることはありません。大クレーンについては区別が必要ですが、それにしても小クレーンなら通れるルートを大クレーンが通れないということはないので、小クレーンが通れるルートを確保できている限りは問題にならないでしょう。
次に、通れるルートの確保について。上述のように、小クレーンが通れるルートを確保していればひとまず手数はともかく転倒数を増やさないように搬出できそうです。逆に言えば、通れるルートを常に確保しておかねばなりません。特に、邪魔をしているのが他のクレーンであればそのクレーンが動けば済みますが、置いたコンテナが邪魔をしているとそのコンテナをどかすことができないのでルートが見つからなくなってしまいます。したがって、常に搬入口と搬出口の間でルートを確保できていることが、実装を楽にするポイントとなりそうです。
また、ルートを確保するということは、盤面上にコンテナが置かれていない空白マスを一定数確保する必要があるということです。したがってむやみに搬入口からコンテナを引き出すと身動きが取れなくなってしまいます。できるだけ速やかに搬出口に連れていけるコンテナを、優先的に搬出したり盤面上に置くことが重要になる気がします。

コードがかなり複雑になってきてしまい、ルールを全て書き下すのも困難なのですが、上記の考察を踏まえて、おおよそ以下のようなルールで転倒数が0になるようなロジックを組みました。

• 搬出口は5つあるので、転倒数が増えないような次に搬出していいコンテナも最大5つある。この5つのうち、最も搬出口に近いものを運ぶ
  • 既に盤面上に引き出されているときは、搬出口までの最短経路を探索し、最もそのコンテナに近いクレーンで運ぶ
  • まだ引き出されていないときは、邪魔になるコンテナを待機場所に移して、盤面に出てきてから搬出口に運ぶ
• 待機場所は原則として以下の8か所(1~8のコンテナがある場所)とする
  
  • この配置だと、盤面に出ているどのコンテナも空きマスを通って搬出口まで運べるため。
• 探索したクレーンの移動経路上に他のクレーンが存在する場合は、そのクレーンを別の場所に予め移動させておくようにする。この処理は再帰的に実行して、クレーン同士が衝突しないようにする
  3回目の提出では、絶対スコアは$121,057,967$点。さらに増加してしまいました。ただ、これも一部の例でハマってしまっていることが要因のようで、うまくいった事例については転倒数が0の状態で搬出を終えることができており、絶対スコアが小さくなっていました。
  seed=0 429点
  

ロジックの穴の修正とPythonへの持ち替え(7日目)

ここまでの改修で、少なくともうまくいく事例ではきっちり転倒数が0になっていることを確認できました。ここからはターン数を削減する必要がありますが、まずはその前にすべてのケースで確実に終了することを目指します。絶対スコアの桁数を考えると、転倒数が正になっているようなケースがあるというより、そもそもすべての搬出が完了していないような事例がありそうだからです。
WAのケースのスコアは相対評価スコアで0点に換算されてしまいます。相対評価の計算は、「全体の絶対スコアの最小値」/「自身の絶対スコア」をベースに計算されるので、これが0になるというのは自身の絶対スコアが無限大になるのと同義です。こういったケースをまずは確実に解決することが重要と考えました。

ほとんどのテストケースでは正常に終了するため、ここで自動化を図ります。そうすると、以下のようなケースが見つかりました。
seed=15

見事な反復横跳びです。
そもそも、序盤に注目すると3番クレーンが8のコンテナを最上段から搬出していたり、まだ10~13が搬出されていないのに14をいきなり搬出してしまったりと、どうも実際の盤面やクレーンの配置と、プログラム内で管理しているデータの間に、差異がありそうだということがわかります。
最初は反復横跳びしている様子だけを見て、掴みに行くコンテナの優先度がうまく設定できておらず、複数のコンテナが同一のクレーンをとりあってしまっているのではないかと考えたのですが、分析していくと上記のようにそもそも盤面更新が正しくできていないことがわかりました。

分析の結果、原因として、他のコンテナやクレーンに完全に周りをふさがれてしまって搬出口までのルートが存在しないにも関わらず、搬出を完了したことにしてしまいクレーンの位置を搬出口に勝手に更新してしまって座標が合わなくなったり、本来移動に失敗するコマンドであるのにも関わらず移動コマンドを追加してしまってつじつまがあわなくなってしまったり…といったことが起こっていることがわかりました。

これらの改修に当たり、付け焼刃でC++を使っていることが仇となり、やりたいことができなくなってきたため、慣れ親しんでいるPythonに持ち替えました。
行動が可能であるかの判定と実際にその操作を行ったことを記録するのを分離することや、搬出口までのルートが存在しない場合の場合分けに加え、ルート上の邪魔なクレーンを移動させる際、再帰処理の中で呼び出し元で既にルートをクリアしているのにそれを再度邪魔するような位置に移動し、再帰が終わらないことを避けるため、既にクリア済みのルートには移動しない処理を加えるなど、予めエラーが発生する可能性をつぶしてあげ、4回目の提出を行いました。
絶対スコアは $19,681$点。大きく改善し、うまくいったテストケースのスコアから予想できる$20,000$点前後の絶対スコアに落ち着きました。手元では500ケースに対してテストを実行しており、それらにおいても正しく搬出できない事例はなかったため、一旦このソースコードをベースに次の一手を考えて良さそうです。
順位表でも400位台まで上がりました。似たような点数の人も結構いる雰囲気です。クレーンを爆破こそしていないものの、複数のクレーンを同時に動かすことはしていないですし、クレーンを操作するルールという観点でもそんなに賢いことはできていないので、今の順位帯はひとまず転倒数が0になるように搬出をできた人たちが集まっているゾーンということになりそうです。
seed=0 428点

操作手順の圧縮(7~8日目)

ひとまず、転倒数0で搬出することはできました。ここからスコアを伸ばす戦略は次の2つだと思います。

• 単一のクレーンの動かし方を賢くする
• 同時に複数のクレーンを動かせるようにする

今回私は、2つ目の「同時に複数のクレーンを動かす」ことを優先しようと考えました。これはクレーンの動かし方を賢くできる限界が見積もりづらかったことと、上位陣のスコアと自分のスコアを比較したときに、明らかに上位陣は複数のクレーンを同時に動かさないと実現が難しいスコアを出していたことが理由です。クレーンは5つあるので、理論上は5倍近く効率化できることになりますし、実際上位陣との相対スコアの比もその感覚に一致しています。実際にはクレーンの動かし方をもっと最適化できるだろうことを考えると、まずはクレーンを同時に動かすことが必須に思えました。

ただ、ここまでの実装では一手ずつクレーンの動きを積み上げるのではなく、搬出口までの経路を探索してまとめて動かすような実装にしていました。現在はクレーンのルートを先に決めて、ルート上にコンテナやクレーンがあればそれをどかしています。つまり、一つのクレーンの動作が先にあって、それが合法になるように盤面を変えていたのです。一方で、複数のクレーンを動かしたいというモチベーションが先に来ると、どうしても一つのクレーンの動きを先に決めることで制約が強くなりすぎて無駄が多くなりそうです。理想的には、毎ターン各クレーンの動作を1手ずつ定めてあげていく方が、クレーンの動きを詰め込むことができそうな気がします。また、このようにできれば、探索系の手法も活用できそうで、うれしいです。

ただ、この方針はあまりに現状の実装とかけ離れており、一手ずつ進めるのは難しそうでいったん断念しました。
代わりに、ここまでのコードで作れた操作列を何らかの方法で圧縮できないか考えてみます。
まず、現在生成された操作列は確実に合法です。ではこの合法性を失わない範囲でターン数を削るにはどうすればよいでしょうか。ここで思いつくのが、操作列のある一つの塊だけをより早いターンにずらしてみて、それで合法性が失われないかどうかを確認することです。
例えば

PRRQ...................
....UPRDDRRRQ..........
.............UPRRRUQ...
....................UUP
.......................

のような操作列があるとき、クレーン1の5ターンから始まる操作列を、矛盾しない範囲で前にずらしてみます。
すると、2ターン目から始めて以下のようにしても、矛盾しないことがわかります。

PRRQ...................
.UPRDDRRRQ.............
.............UPRRRUQ...
....................UUP
.......................

このとき、ずらす前に注目していた塊が終わるターンより後の合法性を確認する必要がない点が重要です。なぜならば、ずらした近傍のターンで合法であれば、その塊の末尾まで操作をトレースした時点で、ずらす前と同じ盤面になっているからです。元の操作列が合法であることは最初に仮定しているため、それと同じ盤面、同じ操作列に行きつけば、残りは確認することなく合法であるといえます。

この操作を塊ごとに繰り返していくことで、合法性を失うことなく簡単に操作列を圧縮することができます。

当初の実装では、操作列を一度ずらすたびに初手から盤面遷移を計算しなおしていましたが、あまりに計算時間がかかりすぎるため、途中からは注目する操作列の塊に突入する直前の盤面を保存しておき、ずらし方を変えるたびにその途中の盤面からだけ、シミュレーションするようにしました。これにより現実的な時間で、圧縮操作が終わるようになりました。

5回目の提出をします。すると、絶対スコアは$8,704$点ととうとう4桁になりました。順位表でも100位まで一気に上がりました。ビジュアライザも以下のように、同時にクレーンが動く瞬間も多く、それっぽくなっています。
seed=0 199点

なおこの実装中に、部分的には合法ではあるものの、操作列を前にずらしすぎてしまい元の操作列で掴んでいたコンテナと異なるコンテナを掴んでしまい、後の操作列が成立しないようなケースに遭遇しました。そこで、元の操作列を作るにあたって、コンテナを掴むコマンドを実行する際は、どのコンテナを掴んだかも記録するようにし、非合法な圧縮が発生しないようにしています。

ルールの効率化(8日目)

ひとまず圧縮はできましたが、まだ改善の余地があります。ビジュアライザを見ていると、以下の2つのことが気になりました。
一つは、コンテナを待避させるときにわざわざ遠い列に運んでしまっているケースがあることです。元の位置から遠くても搬出口に近づいているなら問題ないのですが、極端なケースでは、0行目にある1番のコンテナを4行目の待避スペースに置き、その後0行目の搬出口に運ぶような事例がありました。これはもったいないです。
こうしたケースが起こりづらくなるよう、どの待避スペースを選択するかのルールとして、現在地からの待避スペースまでの距離＋待避スペースから搬出口までの距離が最小になるようなものを選ぶようにしました。
もう一つは、一つのコンテナに負担が集中していることです。特に直前まで他のコンテナを運んでいるクレーンが続けて別のコンテナを運ぶパターンがいくつかありました。操作列を圧縮するためには、できるだけ複数のクレーンが盤面の違う位置を移動していることが重要なのですが、現在コンテナを運ぶクレーンを選ぶルールとして、単にそのコンテナから最も近いクレーンを採用していることもあり、たまに一つのクレーンが延々と仕事をしているだけになっていることがありました。そこで、クレーンを選ぶ際のルールとして、コンテナまでの距離だけでなく、直前までコンテナを運んでいたかどうかも考慮するようにしました。
この2つの改修により、絶対スコアは$8,079$点と、1割程度改善することができました。
この提出時点で、一瞬ではありますが順位も2桁になり、満足感がありました。

次の手がなくなる

これ以降、次の一手が打てず、結局最終日を迎えることになりました。
他にも改善案として

• ルート上の邪魔なクレーンをどかす際、できるだけ小手数でどかす
• 待避先をランダムに変える
• コンテナの待避場所もランダム化する

などがあり、実際に試してはみたのですが、いずれもむしろ悪化する傾向にあり断念しました。
また、乱択したうえで一番よかった操作列を採用するようなアプローチも取りたかったのですが、操作列の圧縮の計算量が非常に重く、複数回実行するのが難しかったため、これも断念しました。結局この操作列を圧縮するアプローチは、圧縮前の操作列をどのように変更すれば圧縮後の操作列が短くなるのか、が直感的ではなかったことが難しいポイントでした。実際、上記の改善はいずれも、操作前の圧縮列で見ると短くなっているものも多かったです。

反省としては、今回最終的に採用したアプローチである「あらかじめクレーンを一つずつ動かして合法な操作列を作る」「その後に、その操作列を合法のままできるだけ短くする」というアプローチは、その後の改善が難しいことが容易に想像できたのに、突っ走ってしまったことです。より改善がイメージしやすい方向に進むことができればよかったのかなと思います。

振り返り

結果としては過去最高の順位だったのでよかったのですが、まだまだできることはありそうでした。特に盤面の評価関数を作りビームサーチをするというアイデアは期間中思いついてはいたので、自分の実装力のなさゆえにそれが実現できなかったことはちょっと残念でした。
複数のクレーンがいるがゆえに、操作が合法かどうかはすべてを同時に判定しないといけないという点が難しかったのですが、盤面を二次元ではなく、時間方向にも拡張して三次元で管理するというアプローチは簡単そうで、本番中に思いつきたかったなと感じています。
この手の盤面上を移動するタイプの問題は考えていて楽しいなぁと思うので、今後も頑張ってみたいです。

注釈

1. つまり、$0~4$のコンテナは$0$行目から、$5~9$のコンテナは$1$行目から…といった具合である。 ↩