【AtCoder】ABC 350 C - Sort | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 394

問題概要

数列 ${1, 2, ..., N}$ を並び替えてできる数列 $A$ が与えられる。次の操作を0回以上 $N - 1$ 回以下行うことで、 $A$ を昇順にソートしたい。操作回数を $K$ として、1行目には $K$ を、続く $K$ 行には各操作で選ぶ整数 $i, j$ を空白区切りで出力せよ。

操作 : $1 \leq i < \leq j \leq N$ を満たす整数の組 $(i, j)$ を選び、 $A_i$ と $A_j$ を入れ替える。

制約

入力はすべて整数。
$2 \leq N \leq 2 \times 10^5$

考察

一見するとバブルソートもしくは選択ソートの手順に見えるが、それらの計算量は $O(N^2)$ であり今回の制約では TLE する。典型のソートアルゴリズムはいったん忘れて、純粋に考えてみよう。

最大操作回数が $N - 1$ 回であることに注目すると、もっとも思いつきやすいのは次のアルゴリズムだろう。

$A$ の先頭から $A_i$ が正しい位置にあるか (先頭から $A_i$ 番目にあるか、つまり $A_i = i$ であるか) どうかを判定していく。
もし正しい位置にない場合、 $A_j = i$ となるような $j (i < j \leq N)$ を求める。
$A_i$ と $A_j$ の位置を入れ替える。

しかし、2の過程で最悪 $N - 1$ 回の探索が必要となり、 TLE となってしまう (例えば、 $A_N = 1$ のとき) 。

これを改善するために、あらかじめ $A_k = k (1 \leq k \leq N)$ となるような $k$ を格納する配列 (ここではposとした) を作成しておき、2, 3の過程をそれぞれ次のように書き換えてみよう。

2'. もし正しい位置にない場合、 $j = pos_i$ とする。
3'. $A_i$ と $A_j$ の位置、 $pos_{A_i}$ と $pos_{A_j}$ の位置をそれぞれ入れ替える。

こうすることでこの部分の処理は定数時間で行うことができるようになり、全体として計算量を $O(N)$ に落とすことができる。

あとはこれを実装していく。各操作で選んだ $i, j$ の組を出力する必要があるので、処理のしやすさからpair型のvector配列にその組を格納している。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using Pair_int = pair<int, int>;

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N + 1), pos(N + 1);
    rep(i, 1, N + 1)
    {
        int a;
        cin >> a;
        A[i] = a;
        pos[a] = i;
    }

    vector<Pair_int> ans;
    rep(i, 1, N + 1)
    {
       if (A[i] != i)
        {
            int j = pos[i];
            swap(A[i], A[j]);
            swap(pos[A[i]], pos[A[j]]);
            ans.push_back(make_pair(i, j));
        }
    }

    cout << ans.size() << endl;
    for (auto p : ans)
    {
        cout << p.first << " " << p.second << endl;
    }
}