Codeforces Round #252 (Div. 2) D. Valera and Swaps
解法
順列の置換は, 一般に巡回置換の積で表すことが出来ます。巡回置換については wikipedia を参考に -> 置換 (数学) - Wikipedia
巡回置換の積それぞれのパーツを分析していきます。一つの巡回置換が A 個の成分で構成されているとすると, 最低でもこの部分を i = p[i] という形にするためには, A-1 回この巡回置換を操作する必要があります。
例を挙げます。例えば 2 5 4 3 1 という順列は, 巡回置換の積で表すと (1 2 5) (3 4) となります。このうち (1 2 5) の部分に着目すると, この部分は, 1 番目と 2 番目を swap した後 1 番目と 5 番目を swap すれば 1, 2, 5 番目については i = p[i] を満たすようになります。操作回数は (1 2 5) の巡回置換の成分数 3 から 1 を引いた 2 回ですね。
2 5 4 3 1 -> 5 2 4 3 1 -> 1 2 4 3 5
ということで, 順列 p が巡回置換 A*B*...*C と表わせ, それぞれの成分数が a, b, ..., c であるとすると, 最低限必要な swap 回数は (a-1) + (b-1) + ... + (c-1) となります。今回はこれを使って問題を解いていきます。
遊んでいると気づきますが, 同じ巡回置換の要素同士で swap をすると, 巡回置換が分裂し, 別々の巡回置換の要素同士で swap をすると, 巡回置換が合成されます。
上の例で言うと, 1 番目と 5 番目は同じ巡回置換の要素同士ですが, ここで 1 番目の数字 と 5 番目の数字 を swap すると 順列は 1 5 4 3 2 となります。これについて再び巡回置換を分析すると, 今度は (1) (2 5) (3 4) となり, 確かに (1 2 5) という巡回置換の要素が (1) (2 5) に分裂しました。
また, 1 番目と 3 番目は別々の巡回置換の要素同士ですが, ここで 1 番目の数字と 3 番目の数字を swap すると, 順列は 4 5 2 3 1 となります。これについて再び巡回置換を分析すると, 今度は (1 4 3 2 5) となり, 確かに (1 2 5) と (3 4) が合成されて 5 つの要素を持つ巡回置換になりました。
で, 上で言ったように巡回置換を i = p[i] とするために最低限必要な swap 回数がわかっているので, 巡回置換を分裂させると, 必要な swap 回数が 1 減り, 合成させると 必要な swap 回数が 1 増えます。
なので, この問題を解くためにはこの辺の事実を上手く使って必要 swap 回数を調整することになります。
最初に巡回置換を調べ, 必要 swap 回数が sum であるとします。このとき,
sum < m ならば, (1, p), (1, q), ... というように 1 と 1 とは別の巡回置換に属する数字を swap させていくことによって必要 swap 回数を増やします。
sum > m ならば, 要素が 2 つ以上の巡回置換を探し, それらのうち辞書順で小さくなる 2 つの数を選べば良いです。
const int MAXN = 3333; int p[MAXN]; bool done[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i]; } int m; cin >> m; int sum = 0; for (int i = 1; i <= n; i++) { if (done[i]) continue; int v = i; int cnt = 0; while (!done[v]) { done[v] = true; cnt++; v = p[v]; } sum += cnt-1; } if (sum == m) { cout << 0 << endl; return 0; } else if (sum < m) { int diff = m-sum; cout << diff << endl; for (int i = 0; i < diff; i++) { memset(done, false, sizeof(done)); int v = 1; while (!done[v]) { done[v] = true; v = p[v]; } for (int j = 2; j <= n; j++) if (!done[j]) { cout << 1 << " " << j; if (i < diff-1) cout << " "; else cout << endl; swap(p[1], p[j]); break; } } } else { int diff = sum-m; cout << diff << endl; for (int t = 0; t < diff; t++) { memset(done, false, sizeof(done)); for (int i = 1; i <= n; i++) { if (done[i]) continue; int v = i; vector<int> memo; while (!done[v]) { done[v] = true; memo.push_back(v); v = p[v]; } if (memo.size() > 1) { sort(memo.begin(), memo.end()); cout << memo[0] << " " << memo[1] ; if (t < diff-1) cout << " "; else cout << endl; swap(p[memo[0]], p[memo[1]]); break; } } } } return 0; }