AT_ahc072_a [AHC072A] Somersault Slimes

高橋くんは、色とりどりのスライムたちを率いる王様である。 日が暮れてきたので、あちこちで遊んでいる仲間たちを、それぞれの色の巣へ帰すことにした。 スライムたちの得意技は、縦に重なり、下の仲間の弾力を借りて跳ぶ「宙返りジャンプ」だ。 王様が指示を出すと、塔の上の一団がくるんとひっくり返って飛んでいく。 巣に着くと、一番上から順に、巣と同じ色のスライムたちが帰っていく。 高橋くんも早く巣に帰って休みたい。 できるだけ少ない指示で仲間全員を巣へ帰せるよう、ジャンプの手順を考えてほしい。 

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 各マスは床または壁である。 盤面には $ 0,1,\ldots,K-1 $ の $ K $ 色のスライムがいる。 スライムは床の上で縦に重なって塔を作ることができる。 異なる色のスライムも同じ塔に重なることができ、融合することはない。 塔の高さはスライムの数であり、**上限は8**である。 スライムのいないマスの高さは0とする。 初期状態では各マスのスライムは高々1匹であり、巣のあるマスにはいない。 各色の巣が1か所ずつあり、スライムは自分と同じ色の巣へ帰ることを目指す。 次の操作「宙返りジャンプ」を最大 $ 100000 $ 回行える。 できるだけ少ない操作回数で、すべてのスライムを帰巣させよ。 #### 宙返りジャンプ 高さ $ h>0 $ の塔があるマス $ (i,j) $ を選び、下に残す匹数 $ k $ 、上下左右の方向 $ d $ 、飛距離 $ \ell $ を指定する。 着地点の操作前の高さを $ g $ として、次の条件をすべて満たさなければならない。 - $ k,\ell $ は整数であり、 $ 0\leq k

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ C_0 $ $ \vdots $ $ C_{N-1} $ - $ 12\leq N\leq20 $ 、 $ 4\leq K\leq12 $ 。 - $ C_i $ は長さ $ N $ の文字列であり、 $ j $ 文字目はマス $ (i,j) $ の初期状態を次のように表す。 - `#`：壁 - `.`：スライムも巣もない床 - `a`〜`l`：色0〜11のスライムが1匹いる床 - `A`〜`L`：色0〜11の巣がある床 - 床は少なくとも $ 2K $ マスあり、上下左右の隣接関係について連結である。 - 英字は大文字・小文字ともに先頭の $ K $ 種類のみが使われ、各大文字はちょうど1回、各小文字は1回以上現れる。

以下の形式で標準出力に出力せよ。 $ t $ 回目の操作の出発点 $ (i_t,j_t) $ 、残す匹数 $ k_t $ 、方向 $ d_t $ 、飛距離 $ l_t $ を、1行に1操作ずつ計 $ T $ 行出力せよ。 > $ i_0 $ $ j_0 $ $ k_0 $ $ d_0 $ $ l_0 $ $ \vdots $ $ i_{T-1} $ $ j_{T-1} $ $ k_{T-1} $ $ d_{T-1} $ $ l_{T-1} $ $ d_t $ は上・下・左・右に対応する `U`、`D`、`L`、`R` の1文字である。 [例を見る](https://img.atcoder.jp/ahc072/BrsBAXF2.html?lang=ja&seed=0&output=sample)

### 得点 操作回数を $ T $ 、操作終了時に盤面に残っているスライムの数を $ E $ とする。 絶対スコアは \\\[ S=T+100000E \\\] とする。 **絶対スコアは小さければ小さいほど良い。** 各テストケースごとに、 $ \mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。 最終順位はコンテスト終了後に実施される、より多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは 0 点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは **CE 以外の結果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50 個 - システムテスト: 2000 個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/ahc072/seeds.txt) (sha256=67cf8463e118af25951c5e583a5b41607e58143174ac6aa6ca8477285fa70323) を公開 #### 相対評価システムについて 暫定テスト、システムテストともに、 CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケースごとの全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認できる各提出のスコアは各テストケースごとの絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出について、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認できるスコアは 0 となるが、順位表には正解したテストケースに対する相対スコアの和が表示される。 #### 実行時間について 実行時間には多少のブレが生じる。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されている。 そのため、実行時間制限ギリギリの提出がシステムテストで TLE となる可能性がある。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせることを推奨する。 ### 入力生成方法 seed=0 の入力は手動で作成されたものであり、暫定テスト、システムテストには含まれない。 それ以外の入力は以下の方法で生成する。 #### 生成パラメータ $ N $ を $ 12 $ 以上 $ 20 $ 以下、 $ K $ を $ 4 $ 以上 $ 12 $ 以下の整数から、それぞれ独立に一様ランダムに生成する。 スライムの密度 $ \rho $ を区間 $ [0.12,0.65) $ 、壁の提案率 $ \beta $ を区間 $ [0,0.40) $ から、それぞれ独立に一様ランダムに生成する。 #### 地形 最初は全マスを床とする。 全マスを一様ランダムな順番に並べる。 並べた順に各マスについて、独立に確率 $ \beta $ で壁への変更を試みる。 変更後も床が少なくとも $ 2K $ マス残り、床が連結である場合に限って壁へ変更する。 #### 巣と初期位置 床から異なる $ K $ マスを一様ランダムに選び、選んだ順に色 $ 0,\ldots,K-1 $ の巣を置く。 巣のない床の数を $ F $ とし、スライムの総数を $ M=\max(K,\mathrm{round}(\rho F)) $ とする。 巣のない床から異なる $ M $ マスを一様ランダムに選び、それぞれにスライムを1匹置く。 #### 色の割り当て 整数区間 $ [0,M-K] $ から、 $ K-1 $ 個の整数をそれぞれ独立に一様ランダムに選ぶ。 同じ値を複数回選んでもよい。 選んだ値を昇順に並べて $ s_1,\ldots,s_{K-1} $ とし、 $ s_0=0 $ 、 $ s_K=M-K $ とする。 各色 $ i=0,\ldots,K-1 $ のスライムの数を \\\[ b\_i=s\_{i+1}-s\_i+1 \\\] とする。 各色 $ i $ を $ b_i $ 個ずつ用意し、全 $ M $ 個の色を一様ランダムに並び替え、初期位置のスライムへ割り当てる。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc072/BrsBAXF2.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc072/BrsBAXF2.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 コンパイルが通らない場合は `rustup update` をお試し下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc072/BrsBAXF2_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中は、seed=0 の入力に対するビジュアライザの出力画像・動画と点数のみ、X で共有できます。 ハッシュタグ #AHC072 と #visualizer を付け、公開アカウントを使用して下さい。 出力文字列、他の入力に対するビジュアライズ結果や点数の共有、および解法・考察に関する言及は禁止されています。 [共有された画像の一覧](https://x.com/search?q=%23AHC072%20%23visualizer&f=live) ### 生成AIの利用に関して 現行の [AtCoder Heuristic Contest 生成AI利用ルール－20250616版](https://info.atcoder.jp/entry/ahc-llm-rules-ja) では、AIエージェントに解答プログラムを実行させ、その実行結果に基づく改善を自動的に繰り返させることを禁止しています。 一方、最新の生成AIでは、ChatGPTのような対話型サービスと、CodexのようなAIエージェントとの区別が曖昧になっています。 対話型サービスであっても、利用者が明示的に指示していない場合に、内部でテストケースの生成、解答プログラムの実行、および実行結果に基づく改善を 自動的に繰り返すことがあります。 一部の参加者は、このような挙動を防ぐため、生成AIに対して禁止事項を明示しています。参加者間の公平性を確保し、現行ルールの趣旨を徹底するため、本コンテストで生成AIを利用する場合は、以下の指示文を各チャットの冒頭に入力するか、各生成AIツールが提供するカスタム指示、プロジェクト指示、または自動的に読み込む指示ファイル （例：`AGENTS.md`、`CLAUDE.md`など）に設定しなければなりません。 ``` I am currently participating in an AtCoder Heuristic Contest, and I will use this generative AI to assist in developing my solution. When using this generative AI, the "AtCoder Heuristic Contest Generative AI Usage Rules - Version 20250616" apply. https://info.atcoder.jp/entry/ahc-llm-rules-en Most importantly, after running the solution program, you must not modify or improve the solution, its approach, or its code based on the execution results unless the user gives a new explicit instruction to do so. You may run the solution program and report its execution results, logs, scores, or other observations. After reporting them, you must stop and wait for a new instruction from the user before making any improvement based on those results. Here, "solution program" refers to any program created or being created for the purpose of solving this contest problem, regardless of whether it was created by the user or by generative AI, and regardless of whether it is still in progress or already complete. ```