Skip to content

トヨタ自動車プログラミングコンテスト2024#5(AHC033)

問題概要

  • 番号がついたコンテナを、N * N (N=5)マスのグリッドの左から右へ、N台のクレーンを使って、指定の順番で搬出したい
  • 毎ターン、各クレーンは、コンテナを掴む、離す、上下左右に移動する、何もしない、クレーンを爆破する、のいずれかをすることができる
    • 各クレーンは同じグリッド上に重なったり、すれ違ったりはできない
    • クレーンは2種類あり、0番だけ大クレーンでそれ以外は小クレーンで、大クレーンは移動先にコンテナがあっても移動できるが、小クレーンはできない
  • できるだけ短いターンで搬出するような操作列を求めよ

時間

  • 240 時間

個人的メモ

クレーンが1台だけの場合

  • シンプルな方法として、大クレーンが1台だけの場合を考えると、他のクレーンを気にしなくて済み、大クレーンは他のコンテナを無視して移動できるのでシンプルに考えられる
  • なので、全部のクレーンでできるだけコンテナを取り出してから、小クレーンは爆破し、大クレーンのみで搬出するアプローチが考えられる
    • (ほぼ問題ないが、最初に搬出するコンテナが取り出せてない場合は詰む場合が存在するので注意)
    • ひとまず、大雑把に「このアプローチでのターン数/5台」が目指すべきターン数として考えられる
  • 一方、クレーンを並列で動かすことを考える場合、小クレーンの方が多いので、小クレーンが動ける方法を考えたい
    • 小クレーンはコンテナやクレーンがあるマスには移動できないので、大クレーンと違った工夫が必要となる
  • 小クレーンがコンテナを搬出できるためには、搬出口までの経路が空いている必要があるため、「経路(道)を作っておく」か「あまりコンテナが出さないようにする」かしたい

一時置き場

  • 番号順に搬出するためには、どうしても一時的にどこかのマスに置いておく必要がある
  • また、小クレーンが搬出できるようにするため、置いているコンテナは搬出の邪魔にならず、「置く＆取る」で2ターン分ロスするので、少ない方が良い
    • ただ、並列で動くため、このロスは必ずしもクリティカルなものではないみたい
  • なので、できるだけそのようなロスが少なくなるような取り出し方を考える

必要な一時置き場の最小数

  • 「dp[r0][r1][r2][r3][r4]:=各行の搬入済み個数の状態がrxのときの必要な最小一次置き場個数」とかで求められる
    • ただ、条件を少しいじって適当に山登り/焼きなまし、ビームサーチとかでも
  • これを求めると、各ケースによって結構違いがあることがわかり、大体平均3〜4マス、最大でも8マスとかであることがわかる
    • seed=0は必要な置き場の数が多くて実は難しめのケースで、seed=38とかは一時置き場が不要な簡単なケース、と違いがあることがわかる
  • また、ここから「取り出す順番」が得られるので、この順番に処理すればよい
  • ただし、多少最小数を超えても一時置き場において良いなど緩和したほうがターン数が減るケースもあるみたい

一時置き場のパターン

  • 道を用意する
    • 行2の部分を道にする
    • 行1と行3の部分を道にする
  • できるだけ端を使う
    • 行0や行4を優先して使う(次に行1や行3)
  • (一時置き場が7箇所とか必要になるケースもあるので、注意)

特定のコンテナを具体的にどの一時置き場に置くか

  • 下記のビームサーチ時に一緒に探索
  • 「必要な一次置き場の最小数」を満たすような順番をたくさん生成して試す
  • 貪欲に空いているところに置く
  • など

クレーン動作の並列化

  • 小クレーン1台で処理する場合は、上記で求めた「取り出す順番」で、一時置き場に置きながら処理していけば、順番に搬出できる
  • これを5台のクレーンで並列化したい

クレーンの1ターンの動きでビームサーチ

  • クレーンの動きは8通りあり、5台分あるため、8^5=32768通りある
    • 実際は、Bは使わない、PとQはコンテナの搬入・一時置き場・搬出地点で決まる、などでもっと少ない
    • コンテナを持っている場合は基本は右方向、持ってない場合は左方向に行きたいはずなので、逆方向や無駄な動きを減らすと4^5=1024ぐらいにできる
    • また、範囲外移動やクレーンの存在でできない動きなどでさらに減る
  • 適当に評価関数を用意して、ビームサーチするなどが考えられる
  • この方法だと、ビーム幅が小さいや評価関数が微妙だと、無駄な動きをして無駄にターン数がかかっていたり、デッドロックが発生したりなどで失敗する可能性がある
  • ただ、良い評価関数やビーム幅を確保できてるなど、十分調整できていれば、この方針で上位にいけていたっぽい

タスク割り当てで貪欲、ビームサーチ

  • (解説放送)
  • クレーンに「指定のコンテナを取りに行って、拾って、移動して、目的地に置く」というタスクを考える
  • 他のクレーンとぶつからない/すれ違わないように移動する方法は、グリッドに時間軸を加えた3次元で考える と、クレーンがいて良い位置がわかるので、これでBFSなどすれば求められる
  • そこで、各クレーンに対して、タスクを割り当てることを考える
    • 割り当てる順番が変わると、先に割り当てた方の経路を後に割り当てた方が避ける経路を取る感じの違いでる
    • コンテナやクレーンの配置によってはどうしても経路が見つからない場合もありえる
  • 空いているクレーンに「取り出す順番」でコンテナを順番に処理する貪欲などでもそこそこ良くなる
    • 順番を変えて貪欲をたくさん試す、順序を焼き鈍す、など
      • 上位ではこの方針の人結構いるっぽい
  • これをビームサーチにしたいが、タスク単位の場合、比較が難しい状態が同じビーム内に並ぶので、評価関数をどうするかが問題になる
    • 最上位は、「考えられる要素を考えて調整」や「必要手数の下限を考える」など

評価関数/評価値

その他工夫

  • 重複排除/多様性確保
    • Zobrist Hash
  • 枝狩り
  • ビットによる高速化
  • など

その他

クレーンで役割を変える

  • 「クレーンXは搬出、クレーンYはコンテナ整理」のように役割をわけて動かすことも考えられる
  • しかし、搬出するクレーンが減るほど並列数が減ってターン数が増えてしまうため、できるだけ全クレーンが並列で搬出できている方が良い

難しいケース

順位表から上位解の見積もり

最短経路

実行時間の劣化、リジャッジ

マルチエージェント経路計画

解説

(50位まで&発言を見つけられた方のみ)