AT_masters2026_qual_a Periodic Patrol Automata (A)

AtCoder社はオフィスの警備を行うロボットを開発中である。 ロボットは前方に壁があるかどうかに応じて状態と行動を変化させる [有限オートマトン](https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3) によって制御される。 オートマトンの状態数、導入するロボットの台数、新たに設置する壁の枚数に応じて必要なコストは変化する。 オフィス全体が定期的に警備されるような、できるだけコストの低い方法を求めてほしい。

$ N\times N $ マスの盤面がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 $ N\times N $ マスの外周は壁で囲まれており、隣接するマス間にも壁が存在する場合がある。 最大で $ N^2 $ 台のロボットを導入できる。 各ロボットにはそれぞれ最大で $ 4N^2 $ 通りの内部状態を設定できる。 ロボットは、前方が壁かどうか（すなわち、現在のマスから現在の向きに1マス進んだ先との間に壁があるかどうか）と現在の内部状態に応じて、直進・右折・左折の行動と次の内部状態を決定するオートマトンによって制御される。 直進(`F`)は現在の向きに1マス移動し、向きは変化しない。 右折(`R`)および左折(`L`)は他のマスへの移動を伴わない、その場での方向転換を指す。 1ステップの動作は次の順に行われる。 まず現在の（位置、向き、内部状態）から前方の壁の有無を判定する。 次に行動と次状態を決定する。 その後行動を実行し、最後に内部状態を次状態に更新する。 $ k $ 番目のロボットを制御するオートマトンの内部状態数を $ m_k $ とする。 $ m_k $ は設計者が任意に定めてよい。 このとき、各状態 $ s=0,1,\cdots,m_k-1 $ について、以下を指定する。 - $ a_{k,s,0} $ : 前方が壁でない場合に、右折(`R`)、左折(`L`)、直進(`F`)のいずれを行うか。 - $ b_{k,s,0} $ : 前方が壁でない場合の次の状態番号。 - $ a_{k,s,1} $ : 前方が壁の場合に、右折(`R`)、左折(`L`)のいずれを行うか。直進(`F`)は選べない。 - $ b_{k,s,1} $ : 前方が壁の場合の次の状態番号。 #### 例 > 内部状態数が2の、以下のようなオートマトンを考える。 > > $ s $ $ a_{k,s,0} $ $ b_{k,s,0} $ $ a_{k,s,1} $ $ b_{k,s,1} $ 0 F 0 R 1 1 R 0 R 0  > > このオートマトンは以下のように動作する。 > > - 内部状態が0のとき、前方に壁がない限り直進し、前方に壁があると右折して内部状態1に遷移する。 > - 内部状態が1のとき、前方に壁があるかどうかに関わらず右折し、内部状態0に遷移する。 > > すなわち、前方に壁がない限り直進し、壁の直前でUターンする動作を繰り返す。 次に、各ロボット $ k $ に対し、初期配置における位置 $ (i_k,j_k) $ と向き $ d_k $ （上: `U`、下: `D`、左: `L`、右: `R`）を決定する。 内部状態の初期値は $ 0 $ である。 ロボット同士は互いに干渉せず、同じマスに複数台存在できる。 最後に、新たな壁を設置する。 壁は任意の隣接2マス間に設置できる。 すでに壁のある位置を指定してもよいが、単にコストが増えるだけで何も起こらない。 新たに導入する壁によって盤面が非連結となっても構わない。 各ロボットの（位置、向き、内部状態）の組は有限であり、同じ組に対する次時刻の（位置、向き、内部状態）の組は一意に定まる。 したがって、一定時間経過後は必ず周期的な行動に入る。 この周期的な行動中にロボットが訪れるマスを、そのロボットの警備対象マスと定義する。 周期的な行動に入る前にのみ訪れるマスは警備対象マスに含めない。 導入するロボットの台数を $ K $ 、全ロボットの内部状態数の総和を $ M=\sum_k m_k $ 、 出力において新たに設置すると指定した壁の本数（出力の `1` の個数）を $ W $ とする。 入力で与えられる係数 $ A_K $ 、 $ A_M $ 、 $ A_W $ に対し、導入コスト $ V $ を以下のように定義する。 \\\[ V = A\_K \\times (K-1) + A\_M \\times M + A\_W \\times W \\\] 全てのマスがいずれかのロボットの警備対象マスとなるような、できるだけ導入コストの低い方法を求めよ。 警備対象マスとならないマスが存在する場合、WA と判定される。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_K $ $ A_M $ $ A_W $ $ v_{0,0} \cdots v_{0,N-2} $ $ \vdots $ $ v_{N-1,0} \cdots v_{N-1,N-2} $ $ h_{0,0} \cdots h_{0,N-1} $ $ \vdots $ $ h_{N-2,0} \cdots h_{N-2,N-1} $ - 盤面サイズ $ N $ は全てのテストケースにおいて $ N=20 $ に固定されている。 - 導入コストの係数 $ A_K, A_M, A_W $ はそれぞれ $ 0 $ 以上 $ 1000 $ 以下の整数である。 - $ v_{i,0} \cdots v_{i,N-2} $ は長さ $ N-1 $ の `0` と `1` からなる文字列であり、 $ j $ 文字目の文字 $ v_{i,j} $ は、マス $ (i, j) $ とマス $ (i, j+1) $ の間に壁がある（`1`）かない（`0`）かを表す。 - $ h_{i,0} \cdots h_{i,N-1} $ は長さ $ N $ の `0` と `1` からなる文字列であり、 $ j $ 文字目の文字 $ h_{i,j} $ は、マス $ (i, j) $ とマス $ (i+1, j) $ の間に壁がある（`1`）かない（`0`）かを表す。 - 初期状態において、全てのマスは互いに到達可能であることが保証されている。

以下の形式で標準出力に出力せよ。 > $ K $ $ m_0 $ $ i_0 $ $ j_0 $ $ d_0 $ $ a_{0,0,0} $ $ b_{0,0,0} $ $ a_{0,0,1} $ $ b_{0,0,1} $ $ \vdots $ $ a_{0,m_0-1,0} $ $ b_{0,m_0-1,0} $ $ a_{0,m_0-1,1} $ $ b_{0,m_0-1,1} $ $ \vdots $ $ m_{K-1} $ $ i_{K-1} $ $ j_{K-1} $ $ d_{K-1} $ $ a_{K-1,0,0} $ $ b_{K-1,0,0} $ $ a_{K-1,0,1} $ $ b_{K-1,0,1} $ $ \vdots $ $ a_{K-1,m_{K-1}-1,0} $ $ b_{K-1,m_{K-1}-1,0} $ $ a_{K-1,m_{K-1}-1,1} $ $ b_{K-1,m_{K-1}-1,1} $ $ v_{0,0}' \cdots v_{0,N-2}' $ $ \vdots $ $ v_{N-1,0}' \cdots v_{N-1,N-2}' $ $ h_{0,0}' \cdots h_{0,N-1}' $ $ \vdots $ $ h_{N-2,0}' \cdots h_{N-2,N-1}' $ - $ K $ は開発するロボットの台数であり、 $ 1\leq K\leq N^2 $ を満たさなければならない。 - $ m_k $ は $ k $ 番目のロボットの内部状態数であり、 $ 1\leq m_k\leq 4N^2 $ を満たさなければならない。 - $ (i_k,j_k) $ は $ k $ 番目のロボットの初期位置であり、 $ 0\leq i_k,j_k\leq N-1 $ を満たさなければならない。 - $ d_k $ は $ k $ 番目のロボットの初期方向であり、上: `U`、下: `D`、左: `L`、右: `R` のいずれかの文字である。 - 各ロボット $ k $ について、内部状態 $ s=0,1,\dots,m_k-1 $ の順にちょうど $ m_k $ 行を出力しなければならない。 - $ a_{k,s,0}, a_{k,s,1} $ は、ロボット $ k $ が内部状態 $ s $ のときの行動を表す。前方が壁でない場合と壁である場合それぞれについて、右折: `R`、左折: `L`、直進: `F` のいずれかを指定する。ただし、 $ a_{k,s,1} $ は `F` であってはならない。 - $ b_{k,s,0}, b_{k,s,1} $ は、ロボット $ k $ が内部状態 $ s $ のときの遷移先の内部状態番号を表す。前方が壁でない場合と壁である場合それぞれについて、 $ 0\leq b_{k,s,0}, b_{k,s,1}\leq m_k-1 $ を満たさなければならない。 - $ v_{i,0}' \cdots v_{i,N-2}' $ は長さ $ N-1 $ の `0` と `1` からなる文字列であり、 $ j $ 文字目の文字 $ v_{i,j}' $ は、マス $ (i, j) $ とマス $ (i, j+1) $ の間に新たに壁を設置する（`1`）かしない（`0`）かを表す。 - $ h_{i,0}' \cdots h_{i,N-1}' $ は長さ $ N $ の `0` と `1` からなる文字列であり、 $ j $ 文字目の文字 $ h_{i,j}' $ は、マス $ (i, j) $ とマス $ (i+1, j) $ の間に新たに壁を設置する（`1`）かしない（`0`）かを表す。 - 壁の設置によって盤面が非連結になっても構わない。

### 得点 導入コストが $ V $ のとき、以下の得点が得られる。 \\\[ 1+\\mathrm{round}\\left(10^6\\times \\max\\left(0,\\log\_2 \\frac{A\_K (N^2-1) + A\_M N^2}{V}\\right)\\right) \\\] 係数 $ A_K $ 、 $ A_M $ 、 $ A_W $ の違いにより、問題は A・B・C の 3 問 に分かれている。 それぞれの問題には 150 個のテストケース があり、各テストケースの得点の合計がその問題に対する提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 各問題に対して獲得した最高得点の総和で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数のチームが得た場合、提出時刻に関わらず同じ順位となる。 ### サンプルプログラム Python での解答例を示す。 このプログラムでは、その場で右回転し続けるロボットを、全てのマスに1台ずつ配置している。 ``` import sys input = sys.stdin.readline N, AK, AM, AW = map(int, input().split()) wall_v = [input().strip() for _ in range(N)] wall_h = [input().strip() for _ in range(N - 1)] K = N * N print(K) for i in range(N): for j in range(N): m = 1 d = 'U' print(m, i, j, d) print('R 0 R 0') for _ in range(N): print('0' * (N - 1)) for _ in range(N - 1): print('0' * N) ``` ### 入力生成方法 #### コスト係数の生成 各問題 A,B,C ごとに、以下の表に記載の範囲(閉区間)から一様ランダムに生成される。 問題 $ A_K $ $ A_M $ $ A_W $ A $ [0,0] $ $ [1,1] $ $ [1000,1000] $ B $ [1000,1000] $ $ [1,10] $ $ [1,10] $ C $ [1000,1000] $ $ [1,1] $ $ [1000,1000] $ #### 壁の生成 $ \mathrm{rand}(L, U) $ を、 $ L $ 以上 $ U $ 以下の整数を一様ランダムに生成する関数とする。 まず、縦方向の壁生成回数 $ X=\mathrm{rand}(1,6) $ と横方向の壁生成回数 $ Y=\mathrm{rand}(1,6) $ を生成する。 壁が一枚も無い状態から開始して、以下のように壁を生成する。 以下の操作を $ X $ 回繰り返す。 1. 壁を生成する方向を上または下からランダムに決定する。 2. 壁の長さを $ L = \mathrm{rand}(5, 15) $ により生成する。 3. 始点 $ (i, j) $ を $ i = \mathrm{rand}(0, N-1),\ j = \mathrm{rand}(0, N-2) $ により選択する。 4. 上方向の場合は $ v_{i-L+1, j}, \cdots, v_{i, j} $ を、下方向の場合は $ v_{i, j}, \cdots, v_{i+L-1, j} $ を `1` に設定する。ただし、添字が盤面の範囲外となる項は無視する。 以下の操作を $ Y $ 回繰り返す。 1. 壁を生成する方向を左または右からランダムに決定する。 2. 壁の長さを $ L = \mathrm{rand}(5, 15) $ により生成する。 3. 始点 $ (i, j) $ を $ i = \mathrm{rand}(0, N-2),\ j = \mathrm{rand}(0, N-1) $ により選択する。 4. 左方向の場合は $ h_{i, j-L+1}, \cdots, h_{i, j} $ を、右方向の場合は $ h_{i, j}, \cdots, h_{i, j+L-1} $ を `1` に設定する。ただし、添字が盤面の範囲外となる項は無視する。 生成した壁に対し、すべてのマスが到達可能であるかを判定する。到達不能な場合は壁を初期化して $ X+Y $ 回の壁生成をやり直す（ $ X,Y $ は再生成しない）。 ### ツール(入力ジェネレータ・スコア計算) - [ローカル版](https://img.atcoder.jp/masters2026-qual/Cy1HtjaW.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/masters2026-qual/Cy1HtjaW_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、チーム外とのビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。