Skip to content

第三回マスターズ選手権-予選-

問題概要

  • https://atcoder.jp/contests/masters2026-qual
  • N*Nマスの盤面があり、すべてのマスを警備できるように、ロボットを導入したい
  • ロボットは最大で N^2 台導入できる
    • 各ロボットは、それぞれ最大で4*N^2通りの内部状態を設定できる
      • 前方に壁があるとき/ないときの「行動」と「遷移先」を設定できる
    • 初期状態として、位置と向きを自由に決めることができる
  • ロボットが周期的な行動中に訪れるマスが警備対象マスとなる
  • また、盤面には壁があり、追加することもできる
  • 導入するロボットの台数をK、内部状態の総和をM、追加壁の本数をWとして、コストV = A_K * (K-1) + A_M * M + A_W * W とする
    • A_K, A_M, A_W はそれぞれ問題ごとに異なる
    • 問題A: 台数の制限なし、追加壁コストが大きい
    • 問題B: 台数コストが大きい、内部状態数コストや追加壁コストは小さめ
    • 問題C: 台数コストと追加壁コストが大きい
  • できるだけ導入コストが低い方法を求めよ

時間

  • 360 分

個人的メモ

手でパターンを作る

  • 典型的なものは手で作って考えることができる
  • その場で回転(1マス)
    • 「L 0 L 0」などその場で回転するようにすれば、そのマスに留まる
  • 長方形ぐるぐる
    • 「F 0 L 0」のようにすると、どこかで長方形をぐるぐる回る(または直線を入ったり来たりする)ような感じになる
  • 1列往復
    • 「F 0 L 1」「L 0 L 0」のようにすると壁の範囲で上下に往復するような動きができる
  • 蛇腹往復
    • 6状態ぐらいを使って列をずらしながら行ったり来たりする動きをさせることができる
    • 盤面を短冊上など領域分割してそこを少ない状態のロボット1台で担当する、など
  • 右手法(左手法)
    • 迷路などで、壁に右手を当てて沿うように動くとゴールできるというのを活用して、壁に沿うように動かすことができる
    • 5状態とかで作れる

1台で全面カバー

  • 問題Aでもロボットの台数が増えると状態総数は増えてしまうので、問題B、Cも含めて、ロボット1台でカバーできないか検討する余地がある

マスを頂点として木を作って辺上を移動する

  • 状態数を気にしなければ、マスを頂点とした木を作って、その木の辺を移動すると1台でカバーできる
    • 壁以外で方向転換するには状態が必要になってしまうので、できるだけ直進が多いとうれしい
    • dfs木、パスや木構造を探索する、など
  • 状態自体はループするはずだが、圧縮できるかはあまり自明でなくて、難易度高いかも

少ない状態数で全面カバーできるオートマトンを探す

  • (コンテスト中、開始2時間ぐらいで上位がロボット1台で「平均状態数が9」、開始4時間で「平均状態数が6」みたいなことになっていた)
  • 少ない状態数でどれだけカバーできるか？を調べようとすると、結構カバーできる可能性があることがわかる
オートマトンの探索
  • 全探索(初期状態含む)は状態数m=3でも結構厳しいので、ある程度効率的に探索することを考える必要がある
  • 局所改善(オートマトンの一部の変更(ある状態の一部分だけ変えるとか、何箇所かまとめて変えるとか))が結構効くようで、ベスト解を保持してそれを変えるのをたくさん試す感じだったり、焼きなまし(多点？)などで結構見つかる模様
  • 状態数が多い場合は、遷移しない状態/遷移したら抜け出せない状態(吸収状態)が含まれる場合があり、それらは削る余地がある
初期状態の探索、全面カバーチェック
  • 「周期的な動き」は、単純にマスでの状態をメモしながらシミュレーションして、同じ状態がでたら繰り返しとわかるので、それで求めることができ、全面カバーしているかは、もう一周して確かめるか、カウントして求めるなどできる
    • AIに任せたら全状態空間前計算方式なるもので計算してくれていたが、短く終わってしまうオートマトンなどもあり、無駄が多いためか遅い
  • ロボットは初期状態として(初期位置, 向き)が設定できるため、4*N^2 の探索が必要そうに見える
  • しかし、もし全面カバーしているならば、周期的動きをしているとき、あるマスの4方向いずれかをいずれかの状態indexで必ず通過するはずなので、そこからスタートすると考えると、全マスで調べる必要がない
    • (0,0)の場合は、上と左が壁でマスの移動ができるのは下か右だけなので、2方向 & いずれかの状態index(M通り)の2*M通りだけを調べればよい
    • 開始状態indexが0でない場合は、初期位置を(0,0)にするなら、出力時に状態の順番やindexを入れ替えるようにする必要がある
状態数m=4で全面カバー
  • テストケースにもよるが、状態数m=4で全面カバーできるものがある
  • 動きとしては、壁がないとき、斜めにジグザグに動くような感じ(「F 1 ? ?」「L 2 ? ?」「F 3 ? ?」「R 0 ? ?」のようなもの)など、いくつかある模様
強いパターン
問題B
  • m=4,5あたりと追加壁1,2枚ぐらいでも結構カバーできる模様
埋め込み解
  • 見つかったm=4,5,6あたりの解をできるだけ多くの解をそのままコードに埋め込んで、全面カバーできているか試す、というのが結構有効だったようで、上位は埋め込み解が多かった模様
    • 初期状態(位置や向き)は気にせず、全部そのまま埋め込んで試す
      • (初期状態などのケースごとへの対応が必要かや、汎用度の高い解をどうするか、など考えてしまって手が止まってしまったが、何も考えずに試してみるべきだった)

その他

想定アプローチ

  • https://x.com/wata_orz/status/2028049780539314424
    • できるだけ状態の少ないオートマトンを用意して、以下のように分かれる想定だったとのこと
      • 問題A: 複数オートマトンで対応
      • 問題B: 壁を増やして対応
      • 問題C: 状態多いのを短くするのを頑張る

解説

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