ステップ 1: 対称性に着目する

まず、この問題では、エクササイズで通る経路は必ずマス \((1, N), \dots, (N, 1)\) を通る線で対称な形になっています。これは、入力例の図などからも観察できます。

このため、最初 \(N-1\) 回の移動（つまり \((1, N), \dots, (N, 1)\) のいずれかに到達するまでの経路）が分かれば、残り \(N-1\) 回の移動も求まります。すなわち、\(i + j \leq N+1\) を満たすマス \((i, j)\) のみを考えた「三角形バージョン」の問題を解けばよいことになります。

---

ステップ 2: 実は各マスの移動方向は周期的

これ以降は三角形バージョンの問題について考えます。

次に、この問題の本質を説明します。実は、各マス \((i, j)\) について、このマスを \(1, 2, 3, \dots\) 回目に訪れた直後に移動する方向は、DDD...DDRRR...RR（D が \(i\) 回の後に R が \(j\) 回）の繰り返しになっています。

この性質のイメージ

\((i, j) = (1, 1)\) のときを考えるとイメージが分かりやすいでしょう。このマスからの移動方向は DRDRDRDR... となります。理由は、\((1, 2)\) と \((2, 1)\) を訪れた回数が同じ状態から D に動いて \((1, 2)\) の方がひとつ多くなり、その状態から R に動いて訪れた回数が同じ状態に戻る、が繰り返されるからです。

このような性質が \((1, 1)\) 以外のマスに対しても成り立つ、ということです。

---

ステップ 3: 動的計画法 (DP) を使って答えを求める

ステップ 2 の考察を使うと、\(t\) 回のエクササイズで各マスを訪れる回数を DP で求めることができます。以下の値を計算する DP を考えます。

• \(\mathrm{dp}[i][j]\): \(t\) 回のエクササイズでマス \((i, j)\) を訪れる回数

DP の初期値は \(\mathrm{dp}[1][1] = t\) です。それ以外の値は、マス \((i, j)\) から次のマスに何回流れるか、を考えることによって以下の図のように計算できます（図の例は \(N = 5, t = 100\) の場合）。例えば、マス \((1, 3)\) を \(33\) 回訪れた場合、DRRRDRRRDRRR... の \(33\) 文字目までに D が \(9\) 回、 R が \(24\) 回現れるので、ここからマス \((2, 3), (1, 4)\) に移動するのがそれぞれ \(9, 24\) 回である、といった考え方に基づきます。

この問題では、\(t = K - 1\) として DP の値を求めることになります。そうすると、\(K\) 回目のエクササイズでの移動をシミュレーションでき、答えがわかります。以上より、この問題は計算量 \(O(N^2)\) で解くことができました。

---

解法の証明

まずは三角形バージョンの問題について考えます。この問題では、各マスについて移動方向に周期性が成り立つという性質があり、これを使って問題を解きました。以下、この性質を証明します。

証明で最も重要なアイデアは、差分 \(\mathrm{dp}[i+1][j] - \mathrm{dp}[i][j+1]\) が必ず \(0, 1\) のどちらかになるということです（上の図を観察すると成り立っているのが分かるでしょう）。もしこの事実を認めれば、DP の値が実際に各マスを訪れる回数に一致することが以下のように証明できます。

証明　まずは以下を定義します。

• \(a^{(t)}_{i, j}\): 実際のルールで動いたときに \(t\) 回のエクササイズでマス \((i, j)\) を訪れる回数
• \(b^{(t)}_{i, j}\): 各マスで移動方向が RR...RDD...D の繰り返しになるというルール（★）で動いたときに、\(t\) 回のエクササイズで \((i, j)\) を訪れる回数
  • つまり、ステップ 3 の DP で求まる「\((i, j)\) を訪れる回数」
  • ここで、任意の \(t, i, j\) に対して \(0 \leq b^{(t)}_{i+1, j} - b^{(t)}_{i, j+1} \leq 1\) であることを仮定

任意の \(t\) に対して \(a^{(t)} = b^{(t)}\) が成り立つことを証明すればよいです。\(t\) に関する帰納法で証明します。まず \(t = 0\) のときは \(a^{(t)}_{i, j} = b^{(t)}_{i, j} = 0\) なので明らかに成り立ちます。残りは、\(a^{(t)} = b^{(t)}\) が成り立つと仮定すれば \(a^{(t+1)} = b^{(t+1)}\) も成り立つことを示すことです。

\(b^{(t+1)}_{i, j}\) について、以下の性質が成り立ちます。

1. \(b^{(t+1)}_{i, j} - b^{(t)}_{i, j} = 1\) となる \((i, j)\) の集合は、★のルールで \(t+1\) 回目に動く経路状になっている（それ以外のマスでは \(b^{(t+1)}_{i, j} - b^{(t)}_{i, j} = 0\)）。
2. \(0 \leq b^{(t+1)}_{i+1, j} - b^{(t+1)}_{i, j+1} \leq 1\) が成り立つ。

ここで、経路状に \(b^{(t)}_{i, j}\) の値を \(1\) ずつ加算する方法 \(2^{n-1}\) 通りの中で、2. の条件を満たすものは何でしょうか？実は、エクササイズのルールに従って動く以外あり得ません。これは、マス \((i, j)\) にいるとき、\(b^{(t)}_{i+1, j} - b^{(t)}_{i, j+1} = 0\) であった場合に右方向に動いたらその差分が \(-1\) となってしまい、\(b^{(t)}_{i+1, j} - b^{(t)}_{i, j+1} = 1\) であった場合に下方向に動いたらその差分が \(2\) となってしまい、どちらにせよ 2. の条件を満たさなくなるからです。

したがって、1. の \((i, j)\) の集合は、エクササイズのルールに従って動いた経路に他なりません。すなわち、\(a^{(t+1)} = b^{(t+1)}\) が成り立ちます。

次に、差分が \(0, 1\) のいずれかであることを証明します。ここでは \(i, j \geq 1\) の場合を考え、差分 \(b^{(t)}_{i+1, j-1} - b^{(t)}_{i, j}, b^{(t)}_{i, j} - b^{(t)}_{i-1, j+1}\) が \(0, 1\) のいずれかであると仮定したときに、差分 \(b^{(t)}_{i+1, j} - b^{(t)}_{i, j+1}\) が \(0, 1\) のいずれかであることを証明します。これは場合分けで比較的まっすぐに証明できます。すると、\(i+j\) に関する帰納法でどの差分も \(0, 1\) のいずれかであることが示されます。

\(i = 0\) または \(j = 0\) の場合への対処

\(b_{-1, k+1} = b_{0, k}, b_{k+1, -1} = b_{k, 0}\) と定義することで、\(i, j \geq 1\) の場合と同様に証明できます。

「差分が \(0\) 以上」の証明

\(b^{(t)}_{i+1, j} - b^{(t)}_{i, j+1}\) が最小化されるケースは \(b^{(t)}_{i+1, j-1}, b^{(t)}_{i, j}, b^{(t)}_{i-1, j+1} = (x, x, x)\) となるケース（つまり差分が \(0, 0\) となるケース）です。

ここで、\((i+1, j-1), (i, j), (i-1, j+1)\) から同時に（★のルールで）次のマスに移動を行う、という操作を \(x\) 回繰り返すことを考えます。これは長さ \(i+j+2\) の周期的になり、それぞれは

• \(1\) 回目から \(i\) 回目まで: 全部下方向
• \(i+1\) 回目: \((i+1, j-1), (i, j)\) からは下方向、\((i-1, j+1)\) からは右方向
• \(i+2\) 回目: \((i+1, j-1)\) からは下方向、\((i, j), (i-1, j+1)\) からは右方向
• \(i+3\) 回目から \(i+j+2\) 回目まで: 全部右方向

したがって、各操作においてマス \((i+1, j), (i, j+1)\) は基本的に両方 \(1\) 回訪れることになりますが、例外的に \(i+1\) 回目は \((i+1, j)\) のみ \(1\) 回訪れ、\(i+2\) 回目は \((i, j+1)\) のみ \(1\) 回訪れることになります。よって、\(x\) を \(i+j+2\) で割ったあまりが \(i+1\) のときのみ差分が \(1\) になり、それ以外のとき差分が \(0\) になります。差分がマイナスになることはありません。

「差分が \(1\) 以下」の証明

「差分が \(0\) 以上」の証明とほぼ同様に証明できます。

\(b^{(t)}_{i+1, j} - b^{(t)}_{i, j+1}\) が最大化されるケースは \(b^{(t)}_{i+1, j-1}, b^{(t)}_{i, j}, b^{(t)}_{i-1, j+1} = (x+2, x+1, x)\) となるケース（つまり差分が \(1, 1\) となるケース）です。

ここで、最初にあらかじめ \((i+1, j-1), (i, j)\) からそれぞれ移動を \(2, 1\) 回（★のルールで）行った後、「\((i+1, j-1), (i, j), (i-1, j+1)\) から同時に次のマスに移動を行う」という操作を \(x\) 回繰り返すことを考えます。この繰り返す操作は長さ \(i+j+2\) の周期的になり、それぞれは

• \(1\) 回目から \(i\) 回目まで: 全部下方向
• \(i+1\) 回目から \(i+j\) 回目まで: 全部右方向
• \(i+j+1\) 回目: \((i+1, j-1)\) からは下方向、\((i, j), (i-1, j+1)\) からは右方向
• \(i+j+2\) 回目: \((i+1, j-1), (i, j)\) からは下方向、\((i-1, j+1)\) からは右方向

したがって、各操作においてマス \((i+1, j), (i, j+1)\) は基本的に両方 \(1\) 回訪れることになりますが、例外的に \(i+j+1\) 回目は \((i, j+1)\) のみ \(1\) 回訪れ、\(i+j+2\) 回目は \((i+1, j)\) のみ \(1\) 回訪れることになります。よって、最初の操作で \((i+1, j), (i, j+1)\) にそれぞれ \(1, 0\) 回訪れていることを考えると、\(x\) を \(i+j+2\) で割ったあまりが \(i+j+1\) のときのみ差分が \(0\) になり、それ以外のとき差分が \(1\) になります。差分が \(2\) 以上になることはありません。

これで、三角形バージョンの問題の解法の正当性が証明できました。最後に、元の問題（正方形バージョン）の対称性を証明して、このセクションを終わります。

対称性の証明

\(a^{(t)}_{i, j}\) を \(t\) 回のエクササイズでマス \((i, j)\) を訪れる回数と定義します。対称性を \(t\) に関する帰納法で証明します。\(t = 0\) の場合は明らかです。\(t \geq 0\) について対称性 \(a^{(t)}_{i, j} = a^{(t)}_{N-j-1, N-i-1}\) が成り立つと仮定したとき、\(t+1\) についても対称性が成り立つことを証明することが目標です。

まず、\(t+1\) 回目のウォーキングの経路を \((1, 1) \to (r_1, c_1) \to \dots \to (r_{2N-1}, c_{2N-1})\) として、これが対称であることを証明します。ここでは、\((r_{N-1}, c_{N-1}) \to (r_N, c_N)\) の方向と \((r_N, c_N) \to (r_{N+1}, c_{N+1})\) の方向が異なることを証明します。\((X, Y, Z) = (a^{(t)}_{r_{N-1}+1, c_{N-1}-1}, a^{(t)}_{r_{N-1}, c_{N-1}}, a^{(t)}_{r_{N-1}-1, c_{N-1}+1})\) と定義します（下図も参照）。ここで、三角形バージョンで既に示した結果より、差分 \(X-Y, Y-Z\) は \(0, 1\) のいずれかであり、また \(t+1\) 回目のウォーキングの後は \(Y\) のみが \(1\) 増加しますがこれについても差分が \(0, 1\) のいずれかでなければならないため、\(X-Y = 1, Y-Z = 0\) がいえます。

ここで、対称性の仮定より、\(i+j = N+2\) となる \(3\) つのマス \((i, j)\) で \(X, Y, Z\) に対応している部分があります（上図を参照）。すると：

• \((r_{N-1}, c_{N-1}) \to (r_N, c_N)\) が下方向であれば、\((r_N, c_N)\) の下は \(X\)、右は \(Y\) となります。\(X-Y=1\) なので、\((r_N, c_N)\) からは右方向に進むことになります。
• \((r_{N-1}, c_{N-1}) \to (r_N, c_N)\) が右方向であれば、\((r_N, c_N)\) の下は \(Y\)、右は \(Z\) となります。\(Y-Z=0\) なので、\((r_N, c_N)\) からは下方向に進むことになります。

以上より、どちらのケースでも \((r_{N-1}, c_{N-1}) \to (r_N, c_N)\) の方向と \((r_N, c_N) \to (r_{N+1}, c_{N+1})\) の方向が異なることが示されました。これを前提に、同様の議論で \((r_{N-2}, c_{N-2}) \to (r_{N-1}, c_{N-1})\) の方向と \((r_{N+1}, c_{N+1}) \to (r_{N+2}, c_{N+2})\) の方向が異なることも示せ、最終的には方向がすべて対称になっていることが示されます。以上より、\(t+1\) 回目のウォーキングの経路は対称です。

\(a^{(t)}_{i, j}\) から \(a^{(t+1)}_{i, j}\) で変わる部分は \(t+1\) 回目のウォーキングで訪れるマスであり、これは対称なので、\(a^{(t+1)}\) についても対称性が成り立ちます。

以上より、すべてのウォーキングの経路が対称であり、すべての \(t\) について \(a^{(t)}\) に対称性が成り立つことが証明できました。

実装例 (C++)

#include <string>
#include <vector>
#include <iostream>
using namespace std;

// 答えを求める関数
string solve(int N, long long K) {
	// step #1. 動的計画法
	vector<vector<long long> > dp(N);
	for (int i = 0; i < N; i++) {
		dp[i].resize(N - i);
	}
	dp[0][0] = K - 1;
	for (int d = 0; d < N - 1; d++) {
		for (int i = 0; i <= d; i++) {
			int j = d - i; // マス (i, j) からの流れを考える
			long long p = dp[i][j] / (d + 2);
			int q = dp[i][j] % (d + 2);
			dp[i + 1][j] += (i + 1) * p + min(q, i + 1);
			dp[i][j + 1] += (j + 1) * p + max(q - (i + 1), 0);
		}
	}

	// step #2. K 回目のウォーキングをシミュレーション
	string ans;
	int r = 0, c = 0;
	for (int i = 0; i < N - 1; i++) {
		if (dp[r + 1][c] <= dp[r][c + 1]) {
			ans += 'D';
			r += 1;
		} else {
			ans += 'R';
			c += 1;
		}
	}

	// step #3. 対称性を使って後半の経路を求める
	for (int i = N - 2; i >= 0; i--) {
		if (ans[i] == 'D') {
			ans += 'R';
		} else {
			ans += 'D';
		}
	}

	return ans;
}

int main() {
	int N; long long K;
	cin >> N >> K;
	string ans = solve(N, K);
	cout << ans << endl;
	return 0;
}