\(S\) の \(i \, (1 \leq i \leq N)\) 番目の文字を \(S_i\) と表します。

操作後に UTPC に一致する連続部分文字列が \(l\) 文字目から \(l + 3\) 文字目 \((S_lS_{l + 1}S_{l + 2}S_{l + 3})\) であるとすると、行う操作として次の 2 種類のみを考えればよいです。

1. \(\, l \leq i < j \leq l + 3\) を満たす整数 \(i, j\) を選び、\(S_i\) と \(S_j\) を入れ替える。
2. \(\, l \leq i \leq l + 3\) を満たす整数 \(i\) と、\(j < l\) または \(l + 3 < j\) を満たす整数 \(j\) を選び、\(S_i\) と \(S_j\) を入れ替える。

例えば、\(S = \)UPTC ならば、\(i = 2, j = 3\) として操作 1 を 1 回行うことで良い文字列となります。また、\(S = \)UTUCP ならば、\(l = 1, i = 3, j = 5\) として操作 2 を 1 回行うことで良い文字列となります。

よって、\(1 \leq l \leq N - 3\) を満たす \(l\) を固定したときに必要な操作回数を求めることが出来れば、全ての \(l\) に対して計算を行い、最小値を取ることで答えが求められます。以下では、\(l\) を固定した際の解き方について 2 通りの解法を説明します。

解法 1 : 操作 1 を全探索する

操作 1 と操作 2 が両方必要な場合について考察すると、次のことが成り立ちます。

• 操作 2 の後に操作 1 を行う場合、\(i, j\) を上手く選ぶことで、操作 1 の後に操作 2 を行うように変更できる。

具体的には、異なる整数 \(i, j, k \,(l \leq i, j, k \leq l + 3)\) と、区間 \([l, l + 3]\) の外にある整数 \(x\) に対して、次のように考えます。

1. 操作 2 で \(S_i\) と \(S_x\) を入れ替えた後、操作 1 で \(S_j\) と \(S_k\) を入れ替える \(\rightarrow\) 操作の順番を入れ替えて良い。
2. 操作 2 で \(S_i\) と \(S_x\) を入れ替えた後、操作 1 で \(S_i\) と \(S_j\) を入れ替える \(\rightarrow\) 操作 1 で \(S_i\) と \(S_j\) を入れ替えた後、操作 2 で \(S_j\) と \(S_x\) を入れ替えることにしてよい。

よって、操作 1 を 0 回以上行ってから操作 2 を 0 回以上行うパターンのみ考えれば十分です。\(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) を操作 1 のみで入れ替えるには高々 3 回で十分なので、操作 1 のみによる入れ替えパターンを全て試しても、高々 \(1 + 6 + 6^2 + 6^3 = 259\) 通りとなります。

このそれぞれに対して、「操作 2 を何回行えばUTPC が完成するか \(\cdots (*)\)」を求めれば、答えが計算できます。ここで、操作 2 で \(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) の特定の位置へと移動させたい文字が全て区間 \([l, l + 3]\) の外部にある場合、必要な操作 2 の回数は、\(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) とUTPC の不一致度 (一致しない文字の個数) に等しくなります。また、区間内部の移動は操作 1 による入れ替えで十分である (回数も悪化しない) ことから、上記の場合のみ考えればよいことも分かります。

よって、次の計算によって答えが求められます。なお、2. における「必要な文字が外側にあれば」という場合分けを省略しても正しい答えが得られます。

1. 操作 1 のみによる入れ替えパターンを全て列挙する。
2. 列挙した各々のパターンに対して、必要な文字が外側にあれば、必要な操作 2 の回数 (\(= S_l S_{l + 1} S_{l + 2} S_{l + 3}\) と UTPC の不一致度) を計算する。
3. 各々のパターンに対して、操作 1 の回数と操作 2 の回数を足し、その最小値を求める。

解法 2 : 最短路問題に帰着する

\(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) を操作 1 と操作 2 によって UTPC に変更するための最小回数を求める問題なので、最短路問題として捉えることが出来ます。

すなわち、U, T, P, C からなる長さ 4 の文字列 \(T\) に対して、次のような距離 \(\mathrm{dist}[T]\) を定義すると、\(\mathrm{dist}[\mathrm{``UTPC"}]\) が答えとなります。

\[ \mathrm{dist}[T] = (S_l S_{l + 1} S_{l + 2} S_{l + 3} から T に変更する操作回数の最小値) \]

ここで、操作 2 によって外部から選べる文字は、今までの操作や \(l\) の値に依存せず、入力で与えられる文字列 \(S\) と状態 \(T\) から一意に定まることが重要です。よって、状態数は高々 \(4^4 = 256\) 通り、各状態からの遷移の数は \(6 + 12 = 18\) 通りで十分なので、この最短路問題は幅優先探索などによって解くことが出来ます。

\(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) を始点とする最短路問題を各 \(l\) に対して毎回解く方法は、実装によっては実行時間制限に間に合いますが、より高速化する方法について考えます。ここで、一度始点として用いた文字列が再び \(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) に現れた場合は計算を省略してよいことを用いると、最短路問題を解く回数は高々 \(4^4\) 回で十分です。よって、今まで始点として用いた文字列を管理しながら計算を行うことで、実行時間制限内に計算を終えることが可能です。

補足 1

解法 2 と似ている解法として、操作を逆順に考える方法もあります。すると、\(\mathrm{``UTPC"}\) を始点として \(S_l S_{l + 1} S_{l + 2} S_{l + 3}\) までの距離を求める問題となるので、一回だけ最短路問題を解けば、全ての \(l\) に対して同一の \(\mathrm{dist}\) を使い回すことが出来ます。

補足 2

1 ケースだけ WA が出ていた方は、\(N = 5, S = \)TCUUP を試すと良いかもしれません。答えは 3 (TCUUP \(\rightarrow\) TUUCP \(\rightarrow\) UTUCP \(\rightarrow\) UTPCU など) になります。