けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 350 C - Sort (灰色, 300 点)

順列テク:逆順列を考える 順列 ソートすることが目的の操作の問題 構築 AtCoder AtCoder300点 灰色diff ABC-C そのまま覚えたい易しい教育的典型問題 データ構造テク:どこにその要素があるのかを管理する 操作 操作をK回まで行える 操作:swap

O(N^{2}) の計算量で良いなら簡単。

「どこに値 i の要素があるのか」を管理するというテクニックをここで習得しよう！

問題概要

1, 2, \dots, N の並び替えである順列 A_{1}, A_{2}, \dots, A_{N} が与えられる。これをソートしたい。以下の操作を N-1 回まで実施できる。

  • i, j を選んで、 A_{i} と A_{j} を swap する

ソートするための操作列を 1 つ求めよ (必ず可能であることは示せる)。

制約

  • N \le 2 \times 10^{5}

考えたこと

この手の問題では、最初は計算量を気にせずに考えるとよい。最後に高速化を試みよう。

この問題に対しては、トランプなどでカードが配られて、それを見やすい順に並び替えるときのことを思い出すと、次のような解法が自然に思い浮かぶ。

  • まず、1 を探して、それを左から 1 番目に持ってくる
    • ただし、もともと左から 1 番目が 1 のときは何もしない
  • 次に、2 を探して、それを左から 2 番目に持ってくる
    • ただし、もともと左から 2 番目が 2 のときは何もしない
  • ...
  • 最後に、 N-1 を探して、それを左から N-1 番目に持ってくる
    • ただし、もともと左から N-1 番目が N-1 のときは何もしない

最後を N ではなく、 N-1 までにしているのは、「左から 1, 2, \dots, N-1 までが揃った時点で、 N の位置も自動的に揃っているため」だ。

さて、値 i (= 1, 2, \dots, N-1) について考えているとき、愚直にやると、以下の処理に O(N) の計算量を要する。

A_{i+1}, A_{i+2}, \dots, A_{N} の中から、値が i であるものを探す

そのため、全体の計算量は O(N^{2}) となってしまう。上記の処理を高速化しよう。

　

高速化

上記の処理を高速化するためには、次の情報を管理すればよい！！　この「どこにその要素があるのかを管理するテク」はより高難易度の問題では頻出する！！

  • where[v] ← A_{i} = v であるような i

この値を管理すれば、上記の「 A_{v+1}, A_{v+2}, \dots, A_{N} の中から、値が v であるものを探す」という処理を O(1) の計算量でこなすことができて、全体の計算量も O(N) となるのである。

where の更新

最後に、 A_{i} と A_{j} を swap するときに、この配列 where も更新する必要があることに注意しよう。慣れないと難しいかもしれない。次のようにできる (これは憶えてしまおう)。

swap(where[A[i]], where[A[j]]);
swap(A[i], A[j]);

ここで、1 行目と 2 行目の順序を間違えないように注意しよう。2 行目を先にやってしまうと、1 行目の処理において、更新されてしまった配列 A の情報を活用することとなるためだ。

　

コード

全体的に 0-indexed で実装した。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), where(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        --A[i];
        
        // 値 A[i] があるのは i 番目
        where[A[i]] = i;
    }
    
    // 左から i 番目に、値 i を持ってくる処理をする
    vector<pint> res;
    for (int i = 0; i <= N - 2; ++i) {
        // i 番目がすでに値 i なら何もしない
        if (A[i] == i) continue;
        
        // 値 i がある場所
        int j = where[i];
        
        // A[i] と A[j] を swap する
        swap(where[A[i]], where[A[j]]);
        swap(A[i], A[j]);
        res.emplace_back(i, j);
    }
    
    // 出力
    cout << res.size() << endl;
    for (auto [i, j] : res) {
        cout << i+1 << " " << j+1 << endl;
    }
}