色が \(A_1\) で駒が置かれた頂点 \(1\) つからはじめて、以下を \(i=2,3,\dots,N\) の順に行うことで、各頂点に色が付いた木をつくります。

• 駒の現在地を \(pos\) とする。 \(pos\) の頂点の色が \(A_i\) である場合、なにもしない。 \(pos\) の隣接頂点に色が \(A_i\) のものが存在する場合、 駒をそこへ移動させる。存在しない場合、色が \(A_i\) で \(pos\) に隣接する新たな頂点を作成し、そこに移動する。なお、作成の仕方から隣接頂点の色は常に distinct であることが保証される。

すると数列の状態はこの木上での（その場にとどまることも許した）ウォークに対応しており、操作は \(u\rightarrow v\rightarrow v\rightarrow \dots \rightarrow v\rightarrow u\) という ウォークを \(u\rightarrow u\rightarrow u\rightarrow \dots \rightarrow u\rightarrow u\) というウォークに変更する操作になります。

ウォークの始点・終点を \(start,goal\) とします。操作によってこれらは変わりません。また、とどまる部分を無視した際ウォークが \(start,goal\) を結ぶ単純パスになっていない場合、上記のような \(u,v\) が必ず存在します。よって問題はウォークを \(start,goal\) を結ぶ単純パスに変更する最小コストを求める問題と考えられます。

一連の操作によりウォーク \((v_1,v_2,\dots,v_n)\) が最終的に \((v'_1,v'_2,\dots,v'_n)\) になるものとしたときの最小コストについて考えます。操作によって \(v_i\) が変更される場合、隣接頂点に変更されるので、 \(v_i,v'_i\) の木上での距離の総和は変更にかかったコストで抑えられます。よって変更にかかるコストの総和の下界として\(v_i,v'_i\) の距離の総和が取れますが、この下界はウォークで通る部分だけに着目した部分木において、葉を訪問している部分で操作することで達成可能です。

以上を踏まえて最小コストの計算を行います。まず初期状態のウォークについて、 \(start,goal\) を結ぶパス上から離れている部分 \(\dots \rightarrow a \rightarrow b \rightarrow \dots \rightarrow b \rightarrow a \rightarrow \dots\) （ \(a\) は \(start,goal\) を結ぶパス上の頂点、 \(b\) はパス上の頂点でない ）について考えると、 どのような操作列においても必ず \(b \rightarrow \dots \rightarrow b\) の部分が \(a\) にとどまり続けるウォークに変換された状態を経由します。よってこの部分はあらかじめ \(a\) にとどまり続けるように変換してよく、変換にかかる最小コストは \(a\) との距離の総和で簡単に求まります。これにより初期状態におけるウォークは \(start,goal\) を結ぶパス上を行き来しているとしてよく、以下の問題が解ければいいです。

整数列 \(V=(v_1,v_2,\dots,v_n)\) がある。 \(V\) は

• \(v_1=1, v_n=\max_{1\leq i \leq n} v_i\)
• \(|v_i-v_{i+1}| \in \{0,1\}\)

を満たす。

このような \(V\) に対し、以下の条件を満たす整数列 \(V'=(v'_1,v'_2,\dots,v'_n)\) に対する \(\sum |v_i-v'_i|\) の最小値を求めよ。

• \(v'_1=v_1, v'_n=v_n\)
• \(v'_i \leq v'_{i+1}\)
• \(v'_i \neq v'_{i+1}\) のとき、\(v_i=v'_i, v_{i+1}=v'_{i+1}\) が成り立つ

これは \(dp[k]=\)（ \(v'_k=v_k\) とするときの \(\sum_{k \leq i} |v_i-v'_i|\) の最小値）として、

• \(v_{k+1}=v_k+1\) のとき、 \(dp[k] \leftarrow \min(dp[k],dp[k+1])\)
• \(v_{i}=v_k\) が成り立つ最小の \(i\ (k < i)\) を \(k'\) として \(dp[k] \leftarrow \min(dp[k],dp[k']+\sum_{i=k+1}^{k'}|v_k-v_i|)\)

と計算する動的計画法により \(O(N)\) 時間で求めることができます。