AT_ahc_genai_test_2026_a Dice Delivery

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 各マスには、荷物を高々一つ置くことができる。 荷物には $ 1,2,\ldots,M $ の番号が付いており、それぞれ一つずつ存在する。 初期配置と、各荷物の目的地のマスが与えられる。 目的地は互いに異なる。 サイコロを転がして、これらの荷物をそれぞれの目的地へ運びたい。 サイコロの六つの面は、それぞれ荷物を高々一つ保持できる。 サイコロは初めマス $ (0,0) $ にあり、六つの面はすべて空である。 1 回の操作では、上下左右のいずれかの方向を選び、次の二つの処理を順に行う。 1. サイコロを選んだ方向へ 90 度転がし、隣接するマスへ移動させる。 2. **移動後に床に接している面の荷物と、移動先のマスの荷物を交換する。** 片方だけに荷物がある場合は、その荷物をもう片方へ移し、双方が空の場合は何も起こらない。 交換を行わずに転がすことや、転がさずに荷物を交換することはできない。 盤面の外へ転がす操作は指定できない。 初期状態では、マス $ (0,0) $ と接地面の交換は行われない。 #### 転がす方向と面の対応 現在の各面を、上面 $ T $ 、下面 $ B $ 、北面 $ N $ 、南面 $ S $ 、西面 $ W $ 、東面 $ E $ と呼ぶ。 北は行番号が小さくなる方向、東は列番号が大きくなる方向である。 下表は、転がした**後**の各面が、転がす**前**のどの面であるかを示す。 面が保持する荷物も、その面と一緒に移動する。 その後、上記の交換を行う。 操作 移動先 新しい上面 新しい下面 新しい北面 新しい南面 新しい西面 新しい東面 `U` $ (i-1,j) $ $ S $ $ N $ $ T $ $ B $ $ W $ $ E $ `D` $ (i+1,j) $ $ N $ $ S $ $ B $ $ T $ $ W $ $ E $ `L` $ (i,j-1) $ $ E $ $ W $ $ N $ $ S $ $ T $ $ B $ `R` $ (i,j+1) $ $ W $ $ E $ $ N $ $ S $ $ B $ $ T $ 操作は最大 $ 10000 $ 回行うことができる。 できるだけ多くの荷物を、できるだけ少ない操作回数で目的地へ運んでほしい。 終了時のサイコロの位置と向きは自由である。 盤面の一部を用いた例を示す。 `R`, `D`, `R`, `U`, `L` の順に操作し、荷物 $ 1 $ を $ (0,1) $ から $ (0,2) $ へ、荷物 $ 2 $ を $ (1,1) $ から $ (0,1) $ へ運ぶ。 4 手目で荷物 $ 1 $ 、5 手目で荷物 $ 2 $ を目的地に置く。 2つの荷物を目的地へ運ぶ5手の例

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_{0,0} $ $ \cdots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ \cdots $ $ a_{N-1,N-1} $ $ b_{0,0} $ $ \cdots $ $ b_{0,N-1} $ $ \vdots $ $ b_{N-1,0} $ $ \cdots $ $ b_{N-1,N-1} $ - $ N=16 $ 、 $ 51\le M\le166 $ 。 - $ a_{i,j} $ は初期状態でマス $ (i,j) $ にある荷物の番号を表す。 0 は空であることを表す。 - $ b_{i,j}>0 $ の場合、その番号の荷物の目的地が $ (i,j) $ であることを表す。 $ b_{i,j}=0 $ のマスには目的地が設定されていない。 - $ a $ と $ b $ のそれぞれに、 $ 1,2,\ldots,M $ がちょうど一度ずつ現れる。 それ以外の要素はすべて 0 である。 - $ a_{0,0}=b_{0,0}=0 $ 。

以下の形式で標準出力に出力せよ。 $ t $ 回目の操作の方向を表す文字 $ d_t $ を、`U`、`D`、`L`、`R` のいずれかとして、 $ T $ 行にわたって出力せよ。 > $ d_0 $ $ \vdots $ $ d_{T-1} $ [例を見る](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY.html?lang=ja&seed=0&output=sample)

### 得点 出力した操作回数を $ T $ 、操作終了時点で目的地のマスに置かれていない荷物の個数を $ E $ とする。 絶対スコアは \\\[ 1+T+10000E \\\] である。 **絶対スコアは小さいほど良い。** 各テストケース毎に、絶対スコアの小さい順での順位に応じた**順位スコア**が得られ、その和が提出の得点となる。 順位スコアは以下のように計算され、高ければ高いほど良い。 コンテストの提出者数を $ n_{submit} $ 、自身より小さい絶対スコアを獲得した参加者の人数を $ n_{lose} $ 、自身と等しい絶対スコアを獲得した他の参加者の人数を $ n_{tie} $ とする。この時、このテストケースにおける順位は $ r=n_{lose}+0.5 n_{tie} $ と定まり、順位スコアは $ \mathrm{round}(10^9\times (1-\frac{r}{n_{submit}})) $ となる。 合計で 100 個のテストケースがある。 コンテスト終了後のシステムテストは行われず、コンテスト中の全ての提出のジャッジが完了した時点の順位表がそのまま最終順位となる。 不正な出力や制限時間超過をした場合、そのテストケースの順位スコアのみ 0 点となる。 #### 相対評価システムについて 順位表には、 CE 以外の結果を得た一番最後の提出のみが反映される。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認できる各提出のスコアは各テストケースごとの絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出について、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認できるスコアは 0 となるが、順位表には正解したテストケースに対する順位スコアの和が表示される。 ### 入力生成方法 $ \operatorname{uniform}(L,U) $ は区間 $ [L,U) $ の実数一様乱数とする。 #### パラメータ \\\[ \\rho=\\operatorname{uniform}(0.20,0.65),\\qquad \\sigma=\\exp(\\operatorname{uniform}(0,\\ln16)). \\\] $ N=16 $ 、 $ M=\mathrm{round}(\rho(N^2-1)) $ とする。 $ \rho $ は荷物の密度、 $ \sigma $ は初期位置と目的地の距離の広がりを制御する。 これらの値は入力には含まれない。 #### 初期配置 $ (0,0) $ 以外の $ N^2-1 $ マスを一様ランダムに並べ替える。 その先頭 $ M $ マスを順に $ s_1,\ldots,s_M $ とし、マス $ s_k $ に荷物 $ k $ を置く。 #### 目的地 荷物の番号 $ 1,\ldots,M $ を一様ランダムに並べ替え、以下の処理をその順に行う。 最初は $ (0,0) $ 以外のすべてのマスを、目的地として未使用とする。 荷物 $ k $ の初期位置を $ s_k=(r_k,c_k) $ とする。 目的地として未使用の各マス $ q=(r,c) $ に対し、重み \\\[ w\_k(q)=\\exp\\left(-\\frac{(r-r\_k)^2+(c-c\_k)^2}{2\\sigma^2}\\right) \\\] を計算する。 未使用マスの中から、 $ w_k(q) $ に比例する確率で一つを選び、荷物 $ k $ の目的地とする。 選んだマスを未使用マスの集合から取り除く。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 コンパイルが通らない場合は `rustup update` をお試し下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc_genai_test_2026/UkOQH5WY_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。 ご注意下さい。