\(N \ge 3\) において \(m_{\min} = 2\) となります。

問題文の折りたたまれた「より厳密は」の一部を再掲します。

\((1,2,\dots,N)\) の順列の列 \(P=(P_1,P_2,\dots,P_m)\) に対して、以下の条件を満たすとき \(P\) を良い順列の列と呼びます。

• 任意の \((1,2,\dots,N)\) の順列 \(Q=(Q_1,Q_2,\dots,Q_N)\) に対して、以下の条件を全て満たす正整数列 \(A=(A_1,A_2,\dots,A_k)\) が存在する。
• \(0 \le k \le 2N^2\)
• \(A\) の要素は全て \(1\) 以上 \(m\) 以下
• 数列 \(R=(1,2,\dots,N)\) に対して、以下の操作を \(i = 1,2,\dots,k\) の順に行うと \(R = Q\) となる。
• \(p = P_{A_i}\) とする。\(j = 1,2,\dots,N\) について、\(R_{j} \) を \(R_{p_j}\) で同時に置き換える。

順列を \(1\) 個用意しただけでは良い順列の列になりえないことを証明します。\(i \rightarrow P_{1,i}\) に辺を貼った \(N\) 頂点 \(N\) 辺グラフが連結である必要がありますが、そのような順列を取った場合 \(P_1\) から作れる \(Q\) は \(N\) 個しかありません。\(N \ge 3\) において \(N! > N\) が成り立つため、\(m_{\min} \ge 2\) となります。

\(m_{\min} = 2\) を構成例と共に証明します。\(P_1,P_2\) として以下を選びます。

• \(P_1 = (2,1,3,4,\dots,N)\) (\(1,2\) 番目の要素の swap)
• \(P_2 = (2,3,4,\dots,N,1)\) (左シフト)

簡単のため、\(Q\) に対して \(1,2\) 番目の要素の swap と左シフトを繰り返し行い \(Q=(1,2,\dots,N)\) とすることを目標とします。実際には \(Q_{q_i} = i\) を満たす順列 \(q\) を取り、\(q\) をソートすればよいです。

バブルソートを適用することを考えると、以下のアルゴリズムで \(Q\) がソートできます。

• 以下を \(N\) 回繰り返す。
  • \(i = 1,2,\dots,N\) について、以下を行う。
    • \(i < N\) かつ \(Q_1 > Q_2\) なら \(Q_1,Q_2\) を swap する。
    • \(Q\) を左シフトする。

一般的なバブルソートが上記によって実行されていることが分かります。操作回数は swap が \(Q\) の転倒数回行われるため、最大で \(\frac{N(N-1)}{2} + N^2\) 回です。

計算量は毎回 \(P_1,P_2\) を作用させたり、\(Q\) の左シフトに \(\mathrm{O}(N)\) かけたりしても \(\mathrm{O}(N^3)\) です。バブルソートを適用することを考えると \(\mathrm{O}(N^2)\) にもなります。