AT_awtf2025heuristic_a Group Commands and Wall Planning

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0, 0) $ とし、下方向に $ i $ 、右方向に $ j $ マス進んだ位置の座標を $ (i, j) $ とする。 一部の隣接マス間には壁が存在する。 盤面上には $ K $ 台のロボットが存在する。 $ k $ 番目のロボットの初期位置は $ (i_k, j_k) $ で、目的地は $ (i_k', j_k') $ である。 高橋くんはこれらのロボットを操作して、すべてのロボットが目的地に到達した状態を達成したい。 まずはじめに、以下の二種類の準備を行う。 1. 最初からある壁に加え、任意の隣接マス間に壁を設置できる。 2. ロボットをグループに分割する。各ロボットは1つのグループに属し、同じグループのロボットは同時に操作することができる。 これらの準備は最初の操作を行う前に行い、それ以降に新たに壁を設置したりグループを変更することはできない。 次に、以下の2種類の操作を繰り返し行うことでロボットを移動させる。 1. **グループ命令**: 1つのグループと上下左右の方向を指定し、そのグループに属するすべてのロボットがその方向に1マス移動する。移動先のマスとの間に壁があったり、移動先に他のロボットが存在する場合は移動しない。指定されたグループに属するロボットのうちで、指定した方向に最も進んだ先にあるものから順に移動する。例えば $ (1,0) $ と $ (2,0) $ にロボットがいる状態で上方向を指定した場合、 $ i $ 座標の小さい順に移動するため、まず $ (1,0) $ のロボットが $ (0,0) $ に移動し、次に $ (2,0) $ のロボットが空いた $ (1,0) $ のマスに移動する。 2. **個別命令**: 1台のロボットと上下左右の方向を指定し、指定したロボットがその方向に1マス移動する。移動先のマスとの間に壁があったり、移動先に他のロボットが存在する場合は移動しない。 一度目的地に到達しても、その後の操作によって目的地から離れた場合は、目的地に到達した状態とはみなされない。 操作は最大で $ K N^2 $ 回行うことができる。 できるだけ少ない操作回数で、すべてのロボットを目的地へ誘導せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ i_0 $ $ j_0 $ $ i_0' $ $ j_0' $ $ \vdots $ $ i_{K-1} $ $ j_{K-1} $ $ i_{K-1}' $ $ j_{K-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} $ - すべてのテストケースにおいて、 $ N=30 $ に固定されている。 - $ 10 \leq K \leq 100 $ を満たす。 - $ (i_k, j_k) $ は $ k $ 台目のロボットの初期位置を表す。 - $ (i_k', j_k') $ は $ k $ 台目のロボットの目的地を表す。 - すべての初期位置、すべての目的地はそれぞれ相異なるが、ロボット $ k $ の初期位置とロボット $ k' $ の目的地が等しい可能性はある。 - $ v_{i,0} \cdots v_{i,N-2} $ は長さ $ N-1 $ の `01` からなる文字列であり、その $ j $ 文字目 $ v_{i,j} $ はマス $ (i, j) $ とマス $ (i, j+1) $ の間に壁がある (`1`) かない (`0`) かを表す。 - $ h_{i,0} \cdots h_{i,N-1} $ は長さ $ N $ の `01` からなる文字列であり、その $ j $ 文字目 $ h_{i,j} $ はマス $ (i, j) $ とマス $ (i+1, j) $ の間に壁がある (`1`) かない (`0`) かを表す。 - すべてのマスは互いに到達可能であることが保証されている。

まず、設置する壁の情報を以下の形式で標準出力に出力せよ。 > $ 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} $ - $ v_{i,0}' \cdots v_{i,N-2}' $ は長さ $ N-1 $ の `01` からなる文字列であり、その $ j $ 文字目 $ v_{i,j}' $ はマス $ (i, j) $ とマス $ (i, j+1) $ の間に壁を設置する（`1`）かしない（`0`）かを表す。 - $ h_{i,0}' \cdots h_{i,N-1}' $ は長さ $ N $ の `01` からなる文字列であり、その $ j $ 文字目 $ h_{i,j}' $ はマス $ (i, j) $ とマス $ (i+1, j) $ の間に壁を設置する（`1`）かしない（`0`）かを表す。 - 最初から壁が存在する箇所は `0` と `1` のどちらを出力しても構わない。 次に、グループ分けの情報を以下の形式で標準出力に出力せよ。 > $ g_0 $ $ \cdots $ $ g_{K-1} $ - $ g_k $ は $ k $ 番目のロボットの属するグループを表す $ 0 $ 以上 $ K-1 $ 以下の整数値である。 $ g_k = g_{k'} $ のとき、ロボット $ k $ と $ k' $ は同じグループに属する。 最後に、操作列を次の形式で標準出力に出力せよ。 > $ a_0 $ $ b_0 $ $ d_0 $ $ \vdots $ $ a_{T-1} $ $ b_{T-1} $ $ d_{T-1} $ - $ a_t $ は $ t $ ターン目の操作の種類を指定する1文字である。グループ命令の場合は `g`、個別命令の場合は `i` である。 - $ b_t $ は $ t $ ターン目の操作対象のグループ番号もしくはロボット番号を表す $ 0 $ 以上 $ K-1 $ 以下の整数値である。ロボットが1台も属さないグループが指定された場合は、何も起こらない。 - $ d_t $ は $ t $ ターン目の操作の方向を指定し、以下の1文字である。 - 上: `U` - 下: `D` - 左: `L` - 右: `R` [例を見る](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4.html?lang=ja&seed=0&output=sample)

### 得点 操作回数を $ T $ 、ロボット $ k $ の最終位置と目的地とのマンハッタン距離を $ d_k $ としたとき、以下の絶対スコアを獲得する。 \\\[ T + 100 \\times \\sum\_k d\_k \\\] **絶対スコアは小さければ小さいほど良い。** 各テストケース毎に、 $ \mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。 最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは **CE 以外の結 果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50個 - システムテスト: 2000個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/awtf2025heuristic/seeds.txt) (sha256=063a84b1c0dc9388b0996eed0bc645529c931c139bee6b8e0e84a4faf3e06c40) を公開 #### 相対評価システムについて 暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。 #### 実行時間について 実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性がありま す。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。 ### 入力生成方法 $ \mathrm{rand}(L, U) $ を、 $ L $ 以上 $ U $ 以下の整数値を一様ランダムに生成する関数とする。 #### ロボットの生成 ロボットの台数 $ K $ を $ K = \mathrm{rand}(10, 100) $ により決定する。 ロボットの初期位置は、 $ N^2 $ 個の座標の中から重複しないように一様ランダムに $ K $ 個選んで生成する。 ロボットの目的地も同様に、 $ N^2 $ 個の座標の中から重複しないように一様ランダムに $ K $ 個選んで生成する。 #### 壁の生成 壁の線分数 $ W $ を $ W = \mathrm{rand}(0, 2) $ により生成する。 以下を $ W $ 回繰り返す。 1. 壁を生成する方向を上下左右からランダムに決定する。 2. 壁の長さを $ L = \mathrm{rand}(10, 20) $ により生成する。 3. 縦方向の壁の場合、始点 $ (i, j) $ を $ i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6) $ により選択する。ただし、これまでに生成された縦壁に使用された $ j $ と絶対値の差が $ 4 $ 以下の $ j $ が選ばれた場合は、方向の選択からやり直す。 上方向の場合は $ v_{i-L+1, j}, \cdots, v_{i, j} $ を、下方向の場合は $ v_{i, j}, \cdots, v_{i+L-1, j} $ を `1` に設定する。ただし、盤面外にはみ出した部分は無視する。 4. 横方向の壁の場合、始点 $ (i, j) $ を $ i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5) $ により選択する。ただし、これまでに生成された横壁に使用された $ i $ と絶対値の差が $ 4 $ 以下の $ i $ が選ばれた場合は、方向の選択からやり直す。 左方向の場合は $ h_{i, j-L+1}, \cdots, h_{i, j} $ を、右方向の場合は $ h_{i, j}, \cdots, h_{i, j+L-1} $ を `1` に設定する。ただし、盤面外にはみ出した部分は無視する。 5. 生成した壁に対し、すべてのマスが到達可能であるかを判定する。到達不能な場合は壁を初期化し、 $ W $ 回の反復をやり直す。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/awtf2025heuristic/sJKH3KO4_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。