🦀

AHC033参加メモ

2024/05/31に公開

競技プログラミング

AtCoder

tech

はじめに

トヨタ自動車プログラミングコンテスト（AtCoder Heuristic Contest 033）をやってみて面白かったので、期間中に考えたり試行錯誤したことのメモ。

問題

問題はかなり複雑だが、Visualizerを見てみると分かりやすく、順番にしか取り出せない荷物を反対側に順番に指定された場所から搬出する課題。順番通りでなくても搬出できるのだけど、スコアのペナルティが大きいので、順番通りに指定された場所から搬出する問題だと思った方が良さそう。
5×5のマスのクレーンが5台もいるので、衝突などを考慮するのが面倒となりそうな印象。クレーンを破壊する動作もあるので活用できるか？

クレーン1台で解いてみる

マスにでている荷物の数を最小にする

5×5のマスの中で、左右は搬入口と搬出口なので一時的な荷物置きとして使えるのは3×5で15マス。今後クレーンの移動経路などを考えるとマスの上にでている荷物は少ない方が良さそう。なので、最適な荷物を搬出する順番を動的計画法（DP）で求めた。

マスにでている荷物の最大数が最も小さい
最大数が等しい場合、場所にでている荷物の合計値（平均値）が最も小さい

搬出する荷物の順番

上の例だと、1, 5を搬出するためには、それぞれ3個, 2個の荷物をマスに置かないといけない。ただ、1を搬出すると、マスの上に置かれた2, 3も搬出できるので、1→5の順番で搬出した時のマスの上に置かれる荷物の最大値は3個になり、5→1の順番だと5個になる。
それぞれの状態での選択肢は5つであり、荷物の総数も25個なので、そんなに時間もかからずに導出できる。

タスクに分解する

荷物を搬出する順番を決めたので、次にそれをクレーンに割り当てるタスクに分割する。ここれ、「どの荷物をどこに運ぶか」を1つのタスクとして定義する。搬出する荷物はそのまま搬出口に運べばいいが、一時的にマスに置いておく荷物をどこに置くかについて課題となる。搬出口までの経路上に配置するのが一番コストが低いだろうと予測し、搬出口の列に右から順番に配置することにした。

配置場所については後ほど見直すが、一時的な荷物の保管場所の位置まで含めて「タスク」にするのは最後まで変更しなかった。

1台のクレーンで動かす

クレーンの数が1台の場合は、上述の方法で決めたタスクを順番に割り当てるだけで問題ない。0番クレーンは、荷物の上を通過して荷物を運べるため、経路に関しても最短（マンハッタン距離）で進むことができる。

0番目の問題で340ターンで完了。ここで提出すると上位40%程度の順位だった。

クレーン1台の時

クレーンを2台にする

クレーンの衝突を避ける

0番以外のクレーンは、荷物を持ったまま他の荷物と同じマスに移動できないので、置いてある荷物を壁だと思って幅優先探索で経路を見つけることとした。ただ、経路がない場合、つまり、一時的に配置した荷物が縦に並んでしまい「左右を分断する壁」ができている時、荷物が運べなくなってしまう。これは、タスクに分解した時に、一時的な荷物の位置関係はわかっているので、経路がないタスクに関しては0番クレーンに割り当てるようにフラグをつけることで対応した。

さらにクレーンの衝突を避けるために、クレーンの移動先が決定したら、そこに「壁」を置くこととした。また、すれ違いを避けるために、クレーンの前の位置もマーカーとして残しておき、すれ違いを起こす方向には移動できないような制約もつけている。クレーンの位置はターン毎に変化するので、マップは動的動的に変化する。このため、ターン毎にクレーンの経路計算をするようにした。

また、一番左側にクレーンがいると搬出の邪魔なので、タスクが与えられていないクレーンが右端にいた場合は、1つ左に移動させる処理を入れている。

タスクの割り当て

タスクは、今タスクを割り当てられていないクレーンの中から、運ぶ荷物に（マンハッタン距離で）一番近いクレーンに割り振るようにした。なお、タスクは運ぶ荷物が搬入口を含むマス目上にないと割り当てられない。

割り当てるタスクがない状態で、タスクの割り当てがないクレーンに関しては破壊する処理を行った。カウが増えてきたら移動の邪魔になるかと思ってのことであるが、どのくらい意味があったかは分からない。

2台のクレーンで動かす

2台目のクレーンは、なんとなく0番クレーンに一番遠い4番クレーンにした。0番目の問題で233ターン。まだ無駄な動きが多いみたいだが、とりあえず2つのクレーンで無事動いた。

クレーン2台の時

3台のクレーン

同時に搬出口に向かうクレーン数の制限

クレーンが2台から3台になるときの問題は、クレーンが他のクレーン2台に挟まれて動けなくなることである。特に右上や右下の搬出口から荷物を出した時に、次の搬出しようとするクレーンに挟まれて身動きが取れなくなってしまうことが多い。

クレーンが動けないケース

これを防ぐために、同じ搬出口に向かうクレーンの数を2台までとタスクを割り当てる時にチェックして、制限をつけた。これで動作するようになり、0番目の問題で192ターン。提出すると上位10%未満まではいけた。

クレーン3台の時
クレーンが3台の時

5台のクレーン

複数回試行する

ここからクレーンの数を増やしていくのだが、すべてのケースに対してクレーン5台での解を求めるのが難しかったため、以下のような感じとした。

ターン数の上限（500)を設定し、それまでの結果を返す
クレーンの数を2台から5台に変化させて問題を解き、最もターン数が少なかった解を採用する

あとは、クレーン数が少ない時にしか解けなかった問題を見ながらブラッシュアップしていった。

タスクの割り当て順番を変更する

同時に搬出口に向かうクレーン数に制限をかけたため、タスクの割り当て待ちをするクレーンが増えてしまう。そこでタスクのリストの先頭から先読みして、処理できるタスクは割り当てるようにした。ここで処理できるタスクとは、これまでと同じ以下の条件である

運ぶ荷物がすでにマス上にある
運び先のマスに荷物がない、かつ、同時に搬出口に向かえるクレーン数の上限に達していない

一時的にマス上におかれる荷物の数が増えてしまうが、「運び先のマスに荷物がない」という制限から、ある程度は緩和できる。

操作するクレーンの順番

順番にクレーンを操作していたが、操作するクレーンの順番を以下のように決めた。

荷物を掴む/離すクレーン: 次のターンまで移動しない事が決まっているため
荷物を運ぶクレーン: その中でも $n$ で割った余りが小さい荷物を運んでいるものを優先
荷物の場所に向かっているクレーン
タスクが割り当てられていないクレーン

優先度が高いクレーンの方を先に動かすことで、最短経路を取りやすくなり、後ろのクレーンが「避ける」ことが可能となる。

経路探索アルゴリズムの変更

これまで、ターン毎に荷物や移動済みのクレーンを「壁」だと思って経路を探索していたが、数ターン先を見越して経路を決めるために、クレーンの経路を決めた時に「 $x$ ターン後にクレーンが来る」という情報を各マスに残して、それを避けるように経路を探索するように変更した。
さらに、前のターンで決めた経路を記憶しておき、その経路が変わらずに利用できるかを優先して経路を探索するようにした。

動作例

0番目の問題で114ターン。ただ、他の人の回答も良くなってきているようで順位は上がらずに下っていった。

クレーンが5台の時

ブラッシュアップ

この後は、クレーンが5台の時にうまくいっていない問題について、その原因を調べて改善していくことでブラッシュアップしていった。基本的には搬出口にクレーンが輻輳してしまう傾向になるのでその対策。

一時的な荷物の配置場所の変更

タスクの割り当て順番を変更可能としたことで、最初にタスクプランを作成する時になかった
「左右を分断する壁」ができてしまう。そこで、一時的な荷物の配置場所に制限を設けて「分断する壁」ができないようにする。
具体的には左から3列目と4列目（一般化すると3列目から $n-1$ 列目まで）、さらに真ん中の列には置かないことにした。これにより、左右が分断されることはない。

一時的な荷物を置ける場所

事前に算出している一時的に配置される荷物の最大値は6なので、8マス用意してあれば余裕がある。

一時的な荷物がマス上に置かれる最大値と平均値の分布

到着予測ターン

一時的に置かれていた荷物が、前の荷物が搬出口に到着するより先に到着してしまうのを防ぐ調整。経路探索の時に到着予想ターン数が分かるので、それで荷物を搬出できない可能性があればクレーンを動かさないようにした。例えば、1番の荷物が5ターン後に到着、2番目の荷物が3ターン後に到着する場合は、2番目の荷物を持ったクレーンをすぐには動かさない。これにより、丁度のタイミングで次のクレーンを搬出口に到着させることができる。

割り振っていないタスクに関しては、移動先までのマンハッタン距離を入れておく事で、追い越してしまうタイミングでタスクを割り当てることを避けた。これは、荷物を取りに来るまでのターン数も必要なので、もう少し攻めることもできたかも。

クレーンの避難と破壊

タスクが終わったクレーンは、搬出口に残っていると邪魔なので、真ん中の列までは移動するようにした。タスクのないクレーンは最後に移動するので、他のクレーンの将来の経路に（できるだけ）ならないマスに移動させるようにした。

さらに、荷物を持っていないクレーンが他のクレーンの邪魔になっているにもかかわらず、移動できない時は爆破することにした。破壊するタスクが割り当てられている可能性があるので、その時はタスクを戻すようにした。一度割り当てられたタスクを戻したり、途中で他のクレーンにまかせるといった処理があってもよかったのかもしれない。

バリエーションを増やす

これまでのアルゴリズムでは、200ms未満で答えを導出していた。今回の問題の制限時間は2秒なので、もっと総当たり的な事をやっても良さそうな感じである。そこで荷物を一時的に置く場所にバリエーションを持たせてみた。
具体的には「道」を真ん中でなく他の行にするパターンも作成して、総当たりで導出、最もターン数が少ない答えを返すようにした。これでも650msぐらいなので、もっといろいろやっても良かったのかもしれない。

結果と所管

最終的なプログラムを使って、ローカルでテストした100問中最もターン数が少なかったのは75番の問題で、77ターンであった。
最終的には上位15%以下には入れたので、悪くはないと思うのだが、最後の方は順位が下がっていって、新しいコードを提出しても元の順位までは戻らないので、焦ってしまった。

最もターン数が少なかった例

問題を最初に読んだ時は、これできるのかな？という気はしたけど、やってみると
ロボットをプログラミングしているようで面白かった。なかなか思ったようにクレーンが動いてくれないことにイライラしたり、うまくいったらうれしかったり。今回、ターン毎にクレーンの行動を決めるように始めてしまったのが良かったのか悪かったのかは分からないが、それなりの結果はだせたのではないかと思う。

各試行でのターン数の確率分布関数

最後に各試行で100個の課題を解いた時のターン数の確率密度関数。試行錯誤してターン数が確実に減っているのが分かる。最後のブラッシュアップは、ターン数が多い問題を潰す方向だったので、グラフを細くできている。ただ、最小値をもっと小さくするには別の考え方が必要だったのかも知れない。