Skip to content

AtCoder Heuristic Contest 066

問題概要

  • https://atcoder.jp/contests/ahc066
  • N*N マスの盤面上に、M種類のボールと各ボールに対応したかごがある
  • 盤面は外周は壁で、マスの間にも壁が存在する可能性がある
  • ロボットが、初期状態として(0,0)マスで右を向いており、操作することでボールをすべて対応したかごにいれたい
  • 操作は、基本操作とマクロ操作がある
  • 基本操作
    • F: 現在の向きに1マス進む。壁の場合は動かない
    • R: 現在のマスで時計回りに90度向きを変える
    • L: 現在のマスで反時計回りに90度向きを変える
    • S: ボールの交換操作を行う
      • ボールを持っていて、現在のマスにボールがある場合は、持っているボールと置いてあるボールを交換する
      • ボールを持っていて、現在のマスにボールがない場合は、持っているボールを置く
      • ボールを持っておらず、現在のマスにボールがある場合は、置いてあるボールを掴む
      • ボールを持っておらず、現在のマスにボールがない場合は、何も置きない
  • マクロ操作
    • M: 現在マクロ記録中でなければマクロ記録を開始する。記録中であればマクロ記録を停止し、新たに登録する
    • P: 最後に登録が完了したマクロを再生する。登録マクロがなければ何もしない
  • マクロ展開後の基本操作は最長でT回までしか実行されず、途中で終わる
  • できるだけ短い操作列ですべてのボールを対応するかごに入れよ

時間

  • 239 時間
  • (直前で修正が入ったみたいで開始が1時間遅れた)

個人的メモ

壁の数W

  • 今回は、「壁の数W」が少ないか多いかで、有効なアプローチが違っていた模様
    • (ただ、なぜ差がつくのかはあまりよくわからない)
  • 詳細順位表のInput FilterでW==0とかW==10とかにしてSubRank順で見ると、結構順位が変わる

アプローチ

良いマクロを探す

(壁多めのケースで強かった解法)

  • マクロ(操作P)は1手で遠くの位置に移動できるので、ボールやかごマスへの移動で活用できると操作回数を減らすことができる
  • 良い感じのマクロを先に構築しておき、マクロは固定した状態で各ボールを順番に運ぶようにすることを考える
  • 候補マクロの準備
    • マクロの形状をビームサーチ/Chokudaiサーチ・焼きなまし・乱択/kick・GAなどで探す
      • だいたいは「方向変換＋直進＋方向変換＋直進＋・・・」のような感じのマクロだと遠くに移動できるので嬉しい可能性がある
        • (ただし、形を制限してしまうのでこれ以外の形の良いマクロがある場合は取りこぼすリスクもある)
      • ボールとかご間の最短パスや事前によく出てくる良いマクロを埋め込んでおいたり、なども
    • 「このマクロは良いか？」の評価が難しく、実際に使ってみてどうなるかシミュレーションしてみないと判断しにくいが、訪問順・経路をどうするかの問題もあるので、ちゃんとやろうとすると時間をかなり使ってしまってたくさんのマクロを試すことが難しい
    • 1段階目はざっくり評価して、2段階目でちゃんと評価、みたいなことをしている人が多かった模様
      • 「ボールからかご」への移動は必ず発生するので、その操作回数合計とかターゲットまでの距離を近似評価に使う、など
      • ただ、雰囲気的には「ボールからかご」への移動だけでも十分近似できそうにも見えるが、実際試してみると「かごからボール」の移動も考慮しないと、あんまりよくなかったかも
    • 候補探索時の訪問順最適化は、訪問順もいっしょに局所探索する、最近傍貪欲で処理する、訪問順固定してシミュレーションする、など
  • 訪問順最適化
    • ボールの処理順(訪問順)の最適化
    • Mが小さいときはbitDP、Mが大きいときは局所改善系でよい最適解が見つけられる
      • TSPというか、有向グラフなので、訪問順の部分をrotateする(segmentに分けてswapする)タイプの近傍が有効
  • 区間経路最適化、圧縮
    • ボールやかごなどの目的地への移動をする場合、複数の最短経路がありえる
      • 経路違い、目的地マスでの向きの違い、Pを使うタイミング、など
      • 最短経路でなくても、1、2手程度のロスがあっても再マクロ化しやすい経路が選べたほうが得な場合もある
    • 後半で同じパターンが何度も出現する場合は、そこを再マクロ化し直すことで手数が減らせる可能性がある(圧縮)
      • 多少違いがあってもマクロの操作のキャンセルで対応できる可能性があり、結構詰める要素がある
    • https://x.com/Ang_kyopro/status/2063933912091656668
  • マクロの多段構築
    • 単一マクロの場合でも、マクロ中によく出てくるものがある場合は、それをマクロ登録して2段階構築することで、マクロの構築手数を減らせる
    • 今回は良さげなマクロにFの連続が出やすかったのもあり、それを先にマクロ登録して、次に目的のマクロ作成をPを使って作る、感じにできる
      • 3段階以上も考えられるが、有効なケースは少なかったかも
    • また、1段階目がFFかFFFかで、構築の総操作回数が同じになる場合があるが、1段階目の違いで構築後の位置・方向が変わる
  • 可変マクロ
    • 後から圧縮するときに再マクロ化するとかではなく、最初から2段階以上(4段階とか)のマクロ変化を想定して探索
  • S入りマクロ
    • ボールを掴む・置くためにはSを2回実行する必要があるが、マクロにSが入っている場合はそれを省略できる可能性がある
    • しかし、マクロの中間あたりにSを入れてしまうと、ボールを運んでいる途中で離してしまうことになるので運びにくい
    • マクロの最初か最後であれば、Pの前か後にSをつけることで操作をキャンセルすることができるので、使いやすい可能性がある
      • たとえば、Sをマクロの最初につける場合、SPと実行すればSを打ち消せるし、MSPMを実行すればPのときに最初にSするかを切り替えることができる(マクロの操作のキャンセル)
    • 「S...」や「...S」ではなく「S...S」というパターンも有効っぽい？
      • Pを使った場合は、ボールを掴んで移動して置く、まで含まれる
  • 良いマクロの埋め込み
    • 第三回マスターズ選手権予選のように、あらかじめ良さそうなマクロを求めておき、それを埋め込んでおく、というのが有効だったみたい
      • ケースに依りそうな感じもするが、短すぎのマクロを探索しないようにできたり、長めのマクロを探すための探索が省略できるなどの効果があったのかも
  • ボールの一時置き(再配置)
    • 「ボールiを掴んでかごiまで移動」を1単位で考えると考えやすいが、移動のついでにボールを動かすと良い可能性もある、が、このアプローチの場合は、うまく活用するのが難しかったかも
    • 掴む・置くにSを2回(ボールを交換するなら1回)余分に必要なので、それよりも取りに行く手数が減る必要があるが、手数を詰めていくと得になるケースがほぼないみたいだった
      • AHC059とかの木構造とかで考えるやつ
    • (ただし、過去改変ビームの場合は、結構一時置きしてるみたい)

過去改変ビーム

(壁がない〜少ないケースで強かった解法)

  • 1手ずつ操作を決めるビームサーチ
  • ただし、操作に「過去のある区間をマクロ化したとしてPする」という仮想的な過去改変操作を許すことで、細かくマクロの作り直し・活用ができるようにする
    • 最後にMを実行した後＆最後に使ったPが変わらなければ、任意の区間をMで挟んだことにすればPでその操作を使うことができる
    • コスト3(M2つ＋P)でかなり移動のバリエーションを増やせる
  • 順番にボールを運ぶことを考えるというより、各ボールの対応するかごまでの距離、などの評価関数を用意して良い状態を探索する感じにするのがよい模様
    • ボールを持ってFすればそのボールだけ差分計算できたり、ボールの一時置きやPのときの複雑な状況変化にも対応しやすい
    • 距離計算は今のマクロに依存せずに事前計算しておけるので軽い
  • ただ、実際試してみると、Tを超えないようにする調整が大変だったり、過去改変操作が重く(候補が多く)、操作回数がそこそこあるので差分更新や高速化ができないと結構厳しそう、、、
  • マクロの途中にSを何個も含んで、かつ、ボールの再配置なども許すので、そこで手数に差がついてそうかも

(位置,向き)のグラフ

  • グリッド上での(位置,向き)を頂点としたグラフを考えると、F,L,R操作はコスト1の頂点移動(有向辺)になる
    • 操作Pもコスト1の有向辺とみなせる
      • 遠くに移動できるショートカット辺と考えることができる
  • 現在地から目的マスの方向の4頂点のどれかへの最短経路は、BFSをすれば求められる
    • 双方向BFSにすると、探索量を減らせる可能性もある
  • (操作Sも上記のグラフをさらに頂点倍化してあげればすべてグラフ上で考えることもできる)

マクロの操作のキャンセル

  • もし、マクロの最初か最後が、LならR、RならL、SならS、をPの前か後に置くことでその操作を打ち消すことができる
  • マクロの途中にSを入れてしまうと、Pを使うとボールをかごに運ぶときに途中で置いてしまうが、マクロの最初か最後であれば打ち消しができるので、少しだけならマクロでの操作を短くするような感じのことができる

Pをしたときの次の位置の高速計算

  • ある操作列について、next[y][x][d] := 操作列を実行したときの次の(位置,向き)、みたいなのを考える
  • F連続の圧縮
    • たとえば、連続するF(FF...FFみたいなもの)について、前計算しておくと、1回で次の位置が求められる
    • マクロに採用される操作列は、向き変更、S、F連続、あたりで構成され、向きやSが連続しているものは正規化すると2手以下になり、F連続も上記の前計算をしておくことで、省略することができる(多少高速化になる)
  • 操作列の合成
    • ある操作列2つがあるとき、それぞれのnext配列がある場合は、連続で適用すれば次の位置がわかる
    • next配列全体についても、4 N^2 回で更新すれば、合成した操作列のnext配列が得られる

(コストの先払い)

  • 先にマクロ構築の手数コストを払っておき、マクロ構築を省略してPのみを考えて、操作列を求めた後に、最初に出てきたPをM...Mに置き換える、みたいなことをやるとやや扱いやすかった
  • 過去改変ビームでも、コスト3を使うのではなく、先にMを予約しておく(コスト1ずつ払っておく)的な感じにすると都合がよいかも(変化がなだらかになっているのかも)

その他

ボールがかごに入ったら消える & Tの制限がない場合

ビジュアライザ、ツール自作

解説

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