Skip to content

AtCoder Heuristic Contest 065

問題概要

  • https://atcoder.jp/contests/ahc065
  • N*N マスの倉庫があり、(0, N/2)のマスが搬出口になっている
  • 倉庫の各マスには0からN^2 - 1までの番号がついた箱が置かれており、順番に搬出口から運び出したい
    • もし倉庫内に残っている箱で一番小さい番号の箱が搬出口にある場合、運び出される
  • 倉庫内最大N^2個のループ状のベルトコンベアを設置することができ、1回の操作で、ベルトコンベアと回転方向を指定すると1マス分だけ回転させることができる
    • ただし、各マスについて含まれるベルトコンベアは高々2個まで
    • また、ベルトコンベアはサイズ2が許される(2マスをswapする感じ)
  • できるだけ少ない操作回数で運び出せるようなベルトコンベアの配置と操作を求めよ

時間

  • 4 時間

個人的メモ

アプローチ

1本のハミルトンサイクル(サンプル)

  • サンプルは、1本のハミルトンサイクルを用意する解法
  • 1周する間に目的の番号の箱が搬出口を必ず通るので、操作回数はかかるが、すべての箱を運び出せる

幅2レーン敷き詰め

  • 「2*H」と「W*2」のベルトコンベアを、横方向・縦方向に敷き詰めるように並べる
  • こうすると、目的の箱に注目した時、搬出口とのマンハッタン距離分の操作回数で搬出口に動かすことができる
  • 単純に、目的の番号の箱だけに注目して1つずつ運び出すと、マンハッタン距離の合計分の操作回数で運び出せる
  • ここで、箱iを運び出すときに、もし箱i+1も一緒に搬出口方向に近づくように運べると、次の番号の箱を運ぶときの操作回数が減らせる可能性がある

ビームサーチ

  • 箱iを運び出すときに箱i+1以降もいくつか搬出口に近づくように動かせると手数が減らせる可能性がある
  • 評価値でそれ以降のいくつかの箱の位置を考慮して、ビームサーチなどでよいものを探す
  • 箱iを運び出す操作だけで考えても、搬出口までの経路は複数ありえるので、どの経路を通ると箱i+1以降の距離をついでに減らせるか、を考える感じかも
  • 箱i+1以降(何個かまで)を運び出す操作も操作で許したり、評価関数、レーンの形状や配置を変える、など、バリエーションがある模様

過去改変貪欲

  • (解説放送)
  • 箱iまでを運び出す手順があるとき、それに箱i+1を運び出す手順を追加することを考える
    • ベースは、箱iまでを運び出す手順の最後に箱i+1を運び出す手順を追加するもので、箱iまでを運び出す手順の途中に追加することで、最後の方の手順が減ることが期待される
  • i以下の箱は、操作を追加した場合に位置が変わってしまうと搬出に失敗してしまうので、位置を動かさないようにしておけば、自由に操作を追加できる
  • 移動操作を何処かに入れる
    • 箱iまでを運び出す手順の途中のどこかに箱i+1の移動操作を追加することを考える
    • 運び出す手順を逆順に考えると、ある時刻で、あるマスにいた場合に、箱iを運び出した段階でゴールからの距離がどのぐらいか？を計算することができる
    • なので、箱i+1をそのマスまで移動させれた場合、箱iまでを運び出す手順の後ろにその距離分の操作が追加されることになるので、最小になるところを採用すれば良い
  • 時空間BFS
    • 上記のアプローチはどこか1箇所に移動操作を入れる感じだが、箱iまでを運び出す操作のインデクスもキーにしてcost[index][y][x]を求める
      • 操作indexのタイミングで、位置y,xに移動するために追加操作回数をコストとする
    • 01BFS等で最小コストのパスを見つけて復元すると、上記のアプローチより自由度が高く移動操作を追加できる

ペア解法(回転寿司解法)

  • サイズ2(幅2ではなく2マス)のベルトコンベアは、2つの隣接マスの箱をswapするようなことができる
  • メインの長いサイクル(搬出口を含む)に、大量のサイズ2のベルトコンベアがついているようなものを考える
  • メインのサイクルの各位置について置きたい番号を決めると、サイズ2のベルトコンベアで退避させておき、置きたい位置が来たらswapして置く、的なイメージ
    • 基本は、0から順番に割り当てて、搬出したら次の番号を割り当てる
    • 同じ方向にのみサイクルが回転しているとすると、乗り遅れが起きた場合、もう1周しないと目的の位置に入れられないなどの問題があるが、基本は数周すれば搬出できる
  • 上記の時空間BFSを適用するでも解ける(解説放送)
  • サイクルやサイズ2のベルトコンベアの形状は最適化の余地がある模様

その他

お絵かき

解説

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