E - Minimum Swap Editorial
by 
MMNMM
まず、\(P\) を \((1,2,\ldots,N)\) と一致させるために必要な操作の回数 \(K\) について考察します。
\((1,2,\ldots,N)\) の並べ替えである列 \(P\) に対して、頂点 \(1,\) 頂点 \(2,\ldots,\) 頂点 \(N\) の \(N\) 個の頂点からなるグラフを考え、\(i=1,2,\ldots,N\) に対して頂点 \(i\) と頂点 \(P _ i\) を結ぶ辺を追加します。 このグラフの連結成分の個数を \(C\) としたとき、\(K=N-C\) であることを示します。
証明
グラフのすべての連結成分はサイズ \(1\) 以上のサイクルです。 それぞれの連結成分から頂点を選び \(i _ 1,i _ 2,\ldots,i _ C\) としたとき、それぞれのサイクルは \(i _ k,P _ {i _ k},P _ {P _ {i _ k}},\ldots\ (1\le k\le C)\) と表されます。
\((i,j)\) を選んで操作を行ったときに \(C\) がどのように変化するかを、頂点 \(i\) と頂点 \(j\) が同じ連結成分にあるときとそうでないときのそれぞれについて考えます。
頂点 \(i\) と頂点 \(j\) が同じ連結成分にあるとき、もともとのサイクル \((i,P _ i,P _ {P _ i},\ldots,j,P _ j,P _ {P _ j},\ldots,P ^ {-1} _ i)\ \bigl(\)ただし、\(P ^ {-1} _ i\) で \(P _ x=i\) なる整数 \(x\) を表す\(\bigr)\) は操作で \((P _ i,P _ {P _ i},\ldots,j)\) と \((P _ j,P _ {P _ j},\ldots,i)\) の \(2\) つのサイクルに分かれます。 よって、この操作で \(C\) は \(1\) だけ増加します。
頂点 \(i\) と頂点 \(j\) が異なる連結成分にあるとき、もともとの \(2\) つのサイクル \((i,P _ i,P _ {P _ i},\ldots,P ^ {-1} _ i),(j,P _ j,P _ {P _ j},\ldots,P ^ {-1} _ j)\) は操作で \((j,P _ i,P _ {P _ i},\ldots,i,P _ j,P _ {P _ j},\ldots,P ^ {-1} _ j)\) の \(1\) つのサイクルになります。 よって、この操作で \(C\) は \(1\) だけ減少します。
\(P\) が \((1,2,\ldots,N)\) と等しいとき、かつそのときに限り \(N=C\) です。 \(N\gt C\) のとき、同じ連結成分にある異なる \(2\) 頂点が必ず存在する（\(i\ne P _ i\) なる \((i,P _ i)\) が条件を満たします）ため、\(N\gt C\) である限り必ず \(C\) を \(1\) ずつ増やすことができます。 逆に、\(C\) は一回の操作でたかだか \(1\) しか増えないため、\(K=N-C\) であることが示されました。
上の議論から、\(K=N-C\) 回の操作で \(P\) を \((1,2,\ldots,N)\) と一致させるためには、（操作をする時点での \(P\) に対応する）グラフで同じ連結成分にある \(2\) 頂点を選んで操作を行うことを \(K\) 回行う必要があることがわかります。 逆に、同じ連結成分にある \(2\) 頂点であれば、どの組を選んでもよいことがわかります。
よって、それぞれのサイクルの大きさを求めることで、この問題を \(O(N)\) 時間などで解くことができました。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <ranges>
#include <numeric>
int main() {
using namespace std;
unsigned N;
cin >> N;
vector<unsigned> P(N);
for (auto&& p : P) {
cin >> p;
--p;
}
vector<unsigned> ans(N);
for (const auto i : views::iota(0U, N)) if (!ans[i]) {
auto p{i};
unsigned count{};
do {
++count;
p = P[p];
} while (p != i); // サイクルを検出して
do {
ans[p] = count; // その頂点が属するサイクルの大きさを記録する
p = P[p];
} while (p != i);
}
cout << (reduce(begin(ans), end(ans), 0UL) - N) / 2 << endl;
return 0;
}
posted:
last update: