mayoko’s diary

プロコンとかいろいろ。

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;
}