\(NK\) 頂点で、\(NK\) 個の辺の辺 \((i, P_{i})\) が存在するグラフを \(G\) とします。

最小の操作回数で \(P\) を昇順ソートするには、\(G\) の頂点 \(i, j(i\neq j)\) であって同じ連結成分に属するものを選び、\(P_{i}\) と \(P_{j}\) を入れ替えることを繰り返せば良いです。

このことから連結成分ごとに答えを求め、その総和を出力すればいいことが分かります。以後 \(G\) の連結成分を \(1\) つ選び、そのサイズが \(n\) であるとして、その連結成分に対する答えを考えます。

以下の条件を全て満たすように数列 \(Q = (Q_{1}, Q_{2}, \dots, Q_{n})\) を \(1\) つ選び定義します。

• \(Q\) に含まれる要素はすべて、選んだ連結成分の頂点番号である。
• \(Q_{i + 1} = P_{Q_{i}}\)
• \(Q_{1} = P_{Q_{n}}\)

この \(Q\) を用いた以下の問題の答えを \(f(Q)\) としたとき、\(f(Q)\) は本問題の答えと同じになります。(後述の理由より)

頂点数 \(n\) の木であって、頂点 \(1, 2, \dots n\) を円周上に並べたときに、辺が交差しないものを good な木とします。

木のスコアを \((a, b) \in E\) かつ \(Q_{a} \equiv Q_{b} \pmod{N}\) を満たす整数 \(a < b\) の数とします。

good な木全てに対するスコアの最大値を求めてください。

辺は swap する index の組に対応しています。

\(f(Q)\) は単純な区間 DP を用いると、時間計算量 \(\Theta(n^{3})\) で求められます。具体的には、\(\mathrm{dp}[l][r]\) を \(l\leq i < j < r\) かつ \(Q_{i} \equiv Q_{j} \pmod{N}\) であるような辺を最大何本採用できるかと定義して適切に更新すれば良いです。

ここで \(f(Q)\) を求める問題の good な木の条件に対して、以下の条件を追加しても \(f(Q)\) は変わりません。

• \((a, b) \in E\) かつ \((a, c)\in E\) かつ \(Q_{a} \equiv Q_{b}\equiv Q_{c}\pmod{N}\) かつ \(a < b < c\) となるような \(a, b, c\) が存在しない。

これはそのような \(a, b, c\) が存在したら、辺 \((a, c)\) を取り除いて辺 \((b, c)\) を加えてもスコアが変わらないからです。

よって、区間 DP の更新を以下のように限定しても良いです。

• \(\mathrm{dp}[l][r] \leftarrow \mathrm{dp}[l + 1][r]\)
• \(\mathrm{dp}[l][r] \leftarrow \mathrm{dp}[l + 1][k] + \mathrm{dp}[k][r] + 1\) (\(Q_{l} \equiv Q_{k}\) のときに限る)

上記の更新は \(1\) つ目が \(\Theta(n^{2})\) 回、\(2\) つ目が \(\Theta(n^{2}K)\) 回なので、連結成分ごとの計算量が \(\Theta(n^{2}K)\) となります。

全体の計算量が \(\Theta(N^{2}K^{3})\) になるので、 本問題の制約下で十分高速に解くことができます。

実装例

実装例 C++

実装例 pypy

---

別の問題に帰着できる理由

簡単のため \(n \neq 1\) とします。

\(n - 1\) 回の swap の中で、\(P_{i}, P_{j}\) の swap を行ったなら、\(Q_{a} = i, Q_{b} = j\) を満たす整数 \(a, b\) を用いて、頂点 \(a, b\) を結ぶ辺をはるということをします。

swap から木

このとき、辺が交差するようなはりかたはできません。なぜなら、そのような \(i, j\) は \(G\) 上ですでに異なる連結成分に存在し、そのような \(2\) つの index を swap することは、最小の操作回数で \(P\) を昇順ソートするのに適した操作ではないからです。

また、閉路があってはいけません。\(i, j\) を swap する操作は \(G\) 上 で頂点 \(i, j\) を異なる連結成分に分解する操作に対応するため、辺を追加して閉路になるとき、すでに異なる連結成分に属するからです。

よって、swap する操作を \(f(Q)\) を求める問題の頂点に辺をはる操作に対応させると、辺が交差しないような木になります。

木から swap

任意の good な木の辺集合 \(E\) に対して、\((i, i + 1)\in E\) かつ頂点 \(i\) もしくは頂点 \((i + 1)\) が葉であるような \(i\) が必ず存在します。

存在しないと仮定した場合、葉 \(a\) と 頂点 \(a\) と直接つながっている頂点 \(b\) であって、\(|a - b|\) が最小のものを \(1\) つとると、 \(a < c < b\) の中に葉が存在しないことになりますが、そのような木は存在しないことが示せます。

\((i, i + 1)\in E\) かつ頂点 \(i\) もしくは頂点 \((i + 1)\) が葉であるような \(i\) を \(1\) つ選びます。頂点 \(i + 1\) が葉であるなら \((i, i + 1)\) の swap を初めにすることにし、そうでないなら \((i, i + 1)\) の swap を最後にすることで \(n\) が \(1\) つ小さいケースに帰着できます。このようにすることで木から valid な swap の操作列が構築できることが示せます。