ウォーキングでどう変わるか観察しよう

まずは、1 回のウォーキングを行うと、タイプ C の道路の向きを表す X, Y の文字列がどのように変わるか観察してみましょう。

例えば XXXYXYYXXXYXXXXYYXXY の状態で始めの交差点から出発して最後までウォーキングする場合、以下の図のようになります。

このように、最初の文字が Y になり、残りの文字はすべて 1 文字ずつ右にずれていることが分かります。

なぜそうなるかを考えてみましょう。経路を観察すると、XX...X や YY...Y のかたまりの最初の文字に対応する道路のみを通っています。つまり、XX...X が YX...X に、YY...Y が XY...Y に変わります。これは各かたまりが 1 文字分右にずれることを意味します。

---

文字列の問題に変えてみる

実際には、途中の交差点から出発して、途中の交差点でウォーキングを終えることもできます。この一例を以下の図に示します。

この場合でも本質的には同じです。通った区間の部分文字列だけ「1 文字ずつ右にずれる」となります。

よって、1 回のウォーキングで、文字列は「X または Y を 1 文字挿入した後、それより後ろで 1 文字削除する」の形で変化します。そのため、この問題は以下の文字列の問題に言い換えられます。

問題　長さ \(N\) の文字列 \(s, t\) が与えられます。以下の操作を最小回数行って \(s\) を \(t\) に変える方法を見つけてください。

• 操作：文字列の適当な位置に X または Y を 1 文字挿入し、それより後ろで 1 文字削除する

これは AtCoder 600～700 点レベルの問題です。競技プログラミングでは、このように「できる限り考えやすい形に問題をとらえ直す」ことが重要になることがあります。

---

そして動的計画法へ

新しい問題は 編集距離 を求める問題と似ており、似たような動的計画法 (DP) のアルゴリズムで解くことができます。

具体例として \(s\) が XYXYX、\(t\) が XXYYY の場合を使って説明します。まず、\(s\) を \(t\) に変えるまでの一連の操作で、どこで挿入・削除を行ったかを、イメージしやすいように \(s, t\) を縦に並べて考えてみましょう。

左図の例は「①の挿入と❶の削除を行う」→「②の挿入と❷の削除を行う」で実現可能ですが、右図のように操作することはできません。なぜなら、操作では挿入位置よりも削除位置の方が右でなければならないからです。一般化して考えると、実現可能な条件は以下のようになります。

条件　左から順に挿入・削除の個数を数えていったときに、挿入の回数が削除の回数を一度も下回らない。

理由　もしある \(t\) で「\(t\) 列目までで挿入の個数が削除の個数を下回る」なら、どれかの操作が「\(t\) 列目までの文字を削除し、\(t+1\) 列目以降の文字を挿入する」になってしまう。一方、このような \(t\) が存在しなければ、左図の（①, ❶）→（②, ❷）の順番のように前から順に操作を行えば、きちんと挿入位置よりも削除位置の方が右になる。

新しい問題は「実現可能なように並べるために最小何列必要か」という問題になります。ここで、左から順に表を埋めていくことを考え、以下の値を計算していく DP を考えます。

• \(dp[i][j]\)：最小で何列目まで埋めたときに「\(s\) を \(i\) 文字目まで、\(t\) を \(j\) 文字目まで書いた状態」になるか
• ただし、実現可能であるためには常に \(i \leq j\) でなければならないので、\(i \leq j\) を満たす \(dp[i][j]\) のみ計算する

これは以下の式にしたがって \((i, j)\) の小さい順に計算できます。

\[ dp[i][j] = \begin{cases} dp[i-1][j] + 1 & (i \geq 1) \ \cdots \ \text{最後の列に 1 行目だけ書く場合（削除のケース）} \\ dp[i][j-1] + 1 & (j \geq 1) \ \cdots \ \text{最後の列に 2 行目だけ書く場合（挿入のケース）} \\ dp[i-1][j-1] + 1 & (i \geq 1, j \geq 1, s_i = t_j) \ \cdots \ \text{最後の列に 1, 2 行目両方書く場合} \\ \end{cases} \]

よって、最小の操作回数は計算量 \(O(N^2)\) で求めることができます。

---

最後に答えを復元して出来上がり

DP では最小の操作回数を求めましたが、実際にどんな表の作り方が最適なのかも求めることができます。この方法は、書籍「競技プログラミングの鉄則」 p. 111-114 や、Qiita 記事「意外と解説がない！動的計画法で得た最適解を『復元』する一般的な方法」 にも解説されていますので、知らない方はこの機会にぜひ知っておきましょう。

ここから実際のウォーキングのやり方を復元する方法は色々ありますが、その中でも楽なやり方をひとつ紹介ます。

実際に復元して、\(s\) の \(p_1, p_2, \dots, p_X \ (p_1 < p_2 < \dots < p_X)\) 文字目を削除し、\(t\) の \(q_1, q_2, \dots, q_X \ (q_1 < q_2 < \dots < q_X)\) 文字目を挿入するのが最適だと求まったとします。このとき、先ほどの（①, ❶）→（②, ❷）の順番のように前から順に操作を行うとき、以下の方法で \(s\) を \(t\) に変えることとなります。

• \(i = 1, 2, \dots, X\) の順に以下を行う。
  • 現在の文字列の \(p_i\) 文字目（文字は \(s_{p_i}\) となる）を削除し、\(q_i\) 文字目の前に文字 \(t_{q_i}\) を挿入する。

先ほどの例の場合、\(s\) の \(3, 5\) 文字目が削除され、\(t\) の \(2, 4\) 文字目が「挿入された文字」となりますが、実際に操作が前述のようになっていることが以下の図で確認できます。

元々はウォーキングの方法を求める問題なので、文字列の各操作をウォーキングに直せば、出来上がりです。

操作をウォーキングに直す方法

\(x\) 文字目の文字 \(s_x\) を削除し、\(y\) 文字目の前に文字 \(t_y\) を挿入する操作 \((x \geq y)\) は、以下のウォーキングに対応します。

• 出発地点：\(t_y\) が X なら交差点 \(2y\)、Y なら交差点 \(2y-1\)
• 終了地点：\(s_x\) が X なら交差点 \(2x\)、Y なら交差点 \(2x-1\)

---

解答例

C++ での実装例は https://atcoder.jp/contests/arc172/submissions/50323432 です。

また、Python では以下のように実装できます。Python (PyPy 3.10-v7.3.12) で提出すると実行時間制限内に正解します。

# 入力を受け取る
n = int(input())
s = input()
t = input()

# 動的計画法
INF = 1012345678
dp = [[INF] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(0, n+1):
	for j in range(i, n+1):
		if i >= 1:
			dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
		if j >= 1:
			dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
		if i >= 1 and j >= 1 and s[i-1] == t[j-1]:
			dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1)

# 答えの復元（x は操作回数、p は s で削除する文字の位置、q は t で挿入する文字の位置）
x = dp[n][n] - n
sidx, p = n, []
tidx, q = n, []
while sidx != 0 or tidx != 0:
	if sidx >= 1 and dp[sidx][tidx] == dp[sidx-1][tidx] + 1:
		sidx -= 1
		p.append(sidx)
	elif tidx >= 1 and dp[sidx][tidx] == dp[sidx][tidx-1] + 1:
		tidx -= 1
		q.append(tidx)
	else:
		sidx -= 1
		tidx -= 1
p, q = p[::-1], q[::-1]

# 答えの出力
print(x)
for i in range(x):
	a = q[i] * 2 + (2 if t[q[i]] == 'X' else 1) # 出発する交差点
	b = p[i] * 2 + (2 if s[p[i]] == 'X' else 1) # 終了する交差点
	print(a, b)