AT_ahc063_a [AHC063A] Colorful Ouroboros

高橋くんは「ウロボロス」と名付けた蛇をペットとして飼っている。 この蛇に餌を与えると、しっぽが 1 m 伸び、伸びた部分が餌の色に染まる。 また、自身の胴体を噛みちぎることができ、千切れたしっぽ側は餌となる。 高橋くんはウロボロスに餌を順に与え、体色の並びを自分の好みに変えようと考えた。 ところが手が滑り、餌が部屋中に散乱してしまった。 ウロボロスに指示を出して餌をすべて食べさせ、最終的な体色の並びをできるだけ自分の好みに近づけてほしい。 指示を出す回数は少なければ少ないほど良い。 

$ N \times N $ マスの盤面がある。 左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 盤面上には $ M-5 $ 個の餌が置かれており、各餌には整数 $ 1,\cdots,C $ で表される色が付いている。 この盤面上を蛇が移動する。 長さ $ k $ の蛇は、頭からしっぽに向かって、 $ k $ 個の座標 $ (i_0,j_0),\cdots,(i_{k-1},j_{k-1}) $ と色 $ c_0,\cdots,c_{k-1} $ の列で表される。 $ (i_0,j_0) $ を**頭**、 $ (i_1,j_1),\cdots,(i_{k-2},j_{k-2}) $ を**胴体**、 $ (i_{k-1},j_{k-1}) $ を**しっぽ**と呼ぶ。 しっぽは他と同じ座標であってもよく、それ以外の座標はすべて互いに異なる。 初期状態では、長さ $ 5 $ で、色がすべて $ 1 $ の蛇が $ (4,0),(3,0),(2,0),(1,0),(0,0) $ の位置にいる。 初期状態で蛇が占めるマスには餌は存在しない。 以下の操作を最大で $ 100000 $ ターン繰り返す。 各ターンでは、あなたは上下左右の方向 $ d $ を指示し、以下の順に蛇が行動する。 1. **移動:** まず、蛇がその方向に 1 マス移動する。 頭の位置から $ d $ 方向に 1 マス進んだ先の座標を $ (i_0',j_0') $ とすると、移動後の蛇の座標は $ (i_0',j_0'),(i_0,j_0),\cdots,(i_{k-2},j_{k-2}) $ となる。 ただし、Uターンとなる方向、すなわち $ (i_0',j_0')=(i_1,j_1) $ となる方向、および $ N \times N $ マスの外に出る方向は指定できない。 2. **食事:** 移動先に色 $ c' $ の餌がある場合、蛇の長さは 1 伸び、座標は $ (i_0',j_0'),(i_0,j_0),\cdots,(i_{k-2},j_{k-2}),(i_{k-1},j_{k-1}) $ となり、色は $ c_0,\cdots,c_{k-1},c' $ となる。 3. **噛みちぎり:** 移動後の頭の位置に、移動後の胴体がある場合を考える。 そのインデックスを $ h $ とする。すなわち、 $ 1\leq h\leq k-2 $ であって、移動後の座標列 $ (i_0',j_0'),\cdots,(i_{k-1}',j_{k-1}') $ に対して $ (i_0',j_0')=(i_h',j_h') $ が成り立つとする。 このとき、蛇は自らの胴体を噛みちぎって長さが $ h+1 $ になり、残りのしっぽ側は対応する色の餌に変わる。 すなわち、蛇の座標は $ (i_0',j_0'),\cdots,(i_h',j_h') $ となり、各 $ p=h+1,\cdots,k-1 $ について、 $ (i_p',j_p') $ に色 $ c_p $ の餌が置かれる。 噛みちぎり後はしっぽと頭が同じ座標を共有した状態となる。 なお、食事と噛みちぎりが同一ターンに同時に発生することはない。 好みの色列 $ d_0,\cdots,d_{M-1} $ が与えられる。 できるだけ短い操作列によって、最終的な蛇の色列を好みの色列に近づけてほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C $ $ d_0 $ $ \cdots $ $ d_{M-1} $ $ f_{0,0} $ $ \cdots $ $ f_{0,N-1} $ $ \vdots $ $ f_{N-1,0} $ $ \cdots $ $ f_{N-1,N-1} $ - 盤面サイズ $ N $ は $ 8 $ 以上 $ 16 $ 以下の整数である。 - $ M $ は好みの色列の長さを表し、 $ N^2/4 $ 以上 $ 3N^2/4 $ 以下の整数である。 - 色数 $ C $ は $ 3 $ 以上 $ 7 $ 以下の整数である。 - $ d_0,\cdots,d_{M-1} $ は好みの色列を表し、各 $ d_p $ は $ 1 $ 以上 $ C $ 以下の整数である。また、 $ d_0=\cdots=d_4=1 $ を満たす。 - $ f_{i,j} $ は初期状態においてマス $ (i,j) $ に置かれている餌の色を表す $ 0 $ 以上 $ C $ 以下の整数である。 - $ f_{i,j}=0 $ の場合、そのマスには餌は置かれていない。 - $ 1 \leq f_{i,j} \leq C $ の場合、そのマスには色 $ f_{i,j} $ の餌が置かれている。 - $ f_{0,0}=\cdots=f_{4,0}=0 $ が成り立つ。 - 餌が置かれているマスの数はちょうど $ M-5 $ である。

操作回数を $ T $ とする。 $ t $ ターン目の移動方向を、上下左右に対応する 1 文字 `U`、`D`、`L`、`R` で表し、これを $ a_t $ とする。 このとき、以下の形式で標準出力に出力せよ。 > $ a_0 $ $ \vdots $ $ a_{T-1} $ [例を見る](https://img.atcoder.jp/ahc063/EbfTtMTp.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作列の長さを $ T $ 、操作完了時点における蛇の長さを $ k $ 、蛇の色列を $ c_0,\cdots,c_{k-1} $ とする。 ここで、 $ k $ は $ M $ 未満であってもよい。 また、誤差 $ E $ を、 $ c_p\neq d_p $ であるような $ p=0,\cdots,k-1 $ の個数と定義する。 このとき、以下の絶対スコアが得られる。 \\\[ T + 10000 \\times (E + 2(M-k)) \\\] 絶対スコアは小さいほど良い。 各テストケース毎に、絶対スコアの小さい順での順位に応じた**順位スコア**が得られ、その和が提出の得点となる。 順位スコアは以下のように計算され、高ければ高いほど良い。 コンテストの提出者数を $ n_{submit} $ 、自身より小さい絶対スコアを獲得した参加者の人数を $ n_{lose} $ 、自身と等しい絶対スコアを獲得した他の参加者の人数を $ n_{tie} $ とする。この時、このテストケースにおける順位は $ r=n_{lose}+0.5 n_{tie} $ と定まり、順位スコアは $ \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})) $ となる。 最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、不正な出力や制限時間超過をした場合、そのテストケースの順位スコアのみ0点となる。 システムテストは **CE 以外の結果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50個 - システムテスト: 2000個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/ahc063/seeds.txt) (sha256=daf8cb67f5deb3bcb35e3d34b97a3b7b7a3ee8da1fe1cbe24f39389ad64a6c85) を公開 #### 相対評価システムについて 暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する順位スコアの和が表示されている。 #### 実行時間について 実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。 ### サンプルプログラム(Python) Python での解答例を示す。 このプログラムでは、上下に蛇行しながらすべての餌を順に食べている。 ``` import sys input = sys.stdin.readline N, M, C = map(int, input().split()) d = list(map(int, input().split())) f = [list(map(int, input().split())) for _ in range(N)] ans = [] for _ in range(4, N - 1): ans.append('D') for col in range(1, N): ans.append('R') if col % 2 == 1: for _ in range(N - 1): ans.append('U') else: for _ in range(N - 1): ans.append('D') print('\n'.join(ans)) ``` ### 入力生成方法 $ \mathrm{rand}(L, U) $ を、 $ L $ 以上 $ U $ 以下の整数を一様ランダムに生成する関数とする。 #### $ N $ , $ M $ , $ C $ の生成 - $ N=\mathrm{rand}(8,16) $ - $ M=\mathrm{rand}(\lceil\frac{N^2}{4}\rceil,\lfloor\frac{3N^2}{4}\rfloor) $ - $ C=\mathrm{rand}(3,7) $ #### $ d $ の生成 $ d_0=\cdots=d_4=1 $ とし、残りの $ M-5 $ 個を以下のように生成する。 $ n_0=0 $ , $ n_C=M-5-C $ とし、 $ C-1 $ 個の乱数 $ n_1,\cdots,n_{C-1} $ を $ \mathrm{rand}(0,M-5-C) $ により生成し、昇順に並べる。 これを用いて、各色の個数 $ m_c $ を $ m_c=n_c-n_{c-1}+1 $ により定める。 ただし、 $ m_c>(M-5)/2 $ となる $ c $ が存在する場合は、 $ n $ の生成からやり直す。 各色 $ c $ を $ m_c $ 個ずつ用意し、ランダムな順に並び替えることにより、 $ d_5,\cdots,d_{M-1} $ とする。 #### $ f $ の生成 初期状態で蛇が占める 5 マス $ (4,0),(3,0),(2,0),(1,0),(0,0) $ 以外の $ N^2-5 $ マスからランダムに $ M-5 $ マスを選び、 $ (i_5,j_5),\cdots,(i_{M-1},j_{M-1}) $ とする。 色 $ d_5,\cdots,d_{M-1} $ をランダムに並び替えた列を $ d_5',\cdots,d_{M-1}' $ とする。 これらを用いて、各 $ p=5,\cdots,M-1 $ について、 $ f_{i_p,j_p}=d_p' $ とする。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc063/EbfTtMTp.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc063/EbfTtMTp.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc063/EbfTtMTp_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。