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

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

AtCoder ABC 250 C - Adjacent Swaps (茶色, 300 点)

実はアルゴ式でもよく似た問題をすでに出していました!

algo-method.com

問題概要

 1, 2, \dots, N がこの順に並んでいます。この数列に対して  Q 回のクエリが投げられました。

各クエリでは、値  v が指定されて、次の操作を実行します。


数列中の整数  v に対し、その右隣の要素が存在するならば、その要素と swap する。存在しないならば左隣の要素と swap する


 Q 回の操作を終えたあとの数列を求めてください。

制約

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

考察

最初の注意点として、問題文は  1, 2, \dots, N というように 1 始まりとなっていますが、ここでは  0, 1, \dots, N-1 というように 0 始まりで考えます。与えられるクエリ  v も 1 を引いて考えます。

さて、この問題の難しいところは「クエリが与えられたときに、整数値  v がどこにあるのかが分からなくなる」ことです。

その場合に最もよく採られる解決方法は、次のように「要素がどこにあるか」を表すデータ構造を用意することです!!!(→ 類題たち)


pos[v] ← 数列 val において、要素 v が何番目の要素であるか


このデータは、とくに数列 val が順列であるとき逆順列と呼びます。たとえば val  = (1, 2, 0) のとき、逆順列は pos  = (2, 0, 1) です。

  • 0 は 2 番目の要素です
  • 1 は 0 番目の要素です
  • 2 は 1 番目の要素です

このように逆順列も合わせて考えることで、この問題は解けます。なお、連結リストを用いる別解もあるので、それも後述します。

解法 (1):逆順列も管理する

順列を val、逆順列を pos と表すことにしましょう。そうすれば、次のように考えられます。


  1. v の位置 pp = pos[v] によって取得できる
  2. 位置 p の右隣の位置を p2 = p + 1 とする (右端の場合は p2 = p - 1)
  3. swap(val[p], val[p2]) を実行する

ただしこのとき、逆順列の方も更新が必要であることに注意しましょう。次のようにします。


  1. 位置 p2 の要素の値 v2 = val[p2] を取得する
  2. swap(pos[v], pos[v2]) を実行する

これらの作業は  O(1) で実行できますので、クエリ全体に要する計算時間は  O(Q) となります。

最初に入力を受け取ったり、配列 pos を初期化したりする処理も合わせて、全体の計算量は  O(N + Q) となります。

コード

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

int main() {
    // 初期化 (最初は val, pos ともに 0, 1, ..., N-1)
    int N, Q;
    cin >> N >> Q;
    vector<int> val(N), pos(N);
    for (int i = 0; i < N; ++i) val[i] = pos[i] = i;

    // 各クエリ
    while (Q--) {
        // 入力
        int v;
        cin >> v;
        --v;  // すべて 0 始まりで考える

        int p = pos[v];
        int p2 = (p < N - 1 ? p + 1 : p - 1);
        int v2 = val[p2];

        swap(val[p], val[p2]);
        swap(pos[v], pos[v2]);
    }

    // 出力 (1 始まりに直す)
    for (auto v : val) cout << v + 1 << " ";
    cout << endl;
}

別解:連結リスト

技術的な詳しい話については、アルゴ式の一連の問題集を参考にしてください。

algo-method.com

要素をつなぎ変えたり、削除したり (今回は削除は不要) する処理は、連結リストを用いて容易に表現できます (→ 類題たち)。今回は具体的には次の 2 つのデータを用意しましょう。


  • nex[v] ← 要素 v の次の要素は何か (存在しないなら -1)
  • bak[v] ← 要素 v の前の要素は何か (存在しないなら -1)

これらのデータを逐次更新していきます。計算量はやはり  O(N + Q) となります。

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

int main() {
    // 初期化
    int N, Q;
    cin >> N >> Q;
    vector<int> nex(N, -1), pre(N, -1);
    for (int i = 0; i < N; ++i) {
        if (i + 1 < N) nex[i] = i + 1;
        if (i - 1 >= 0) pre[i] = i - 1;
    }

    // 連結リストの出力
    auto print = [&]() -> void {
        // 先頭を探す
        int v = 0;
        for (; v < N; ++v) if (pre[v] == -1) break;
        while (v != -1) {
            cout << v + 1 << " ";
            v = nex[v];
        }
        cout << endl;
    };

    // 各クエリ
    while (Q--) {
        int v;
        cin >> v;
        --v;

        // v1, v2, v3, v4 の順に繋ぐようにする
        int v1, v2, v3, v4;
        if (nex[v] != -1) {
            // 右隣がある場合
            v1 = pre[v], v2 = nex[v], v3 = v, v4 = nex[v2];
        } else {
            // 右隣がない場合
            v4 = nex[v], v3 = pre[v], v2 = v, v1 = pre[v3];
        }

        // 進行方向をつなぎ変える
        if (v1 != -1) nex[v1] = v2;
        nex[v2] = v3;
        nex[v3] = v4;

        // バック方向をつなぎ変える
        if (v4 != -1) pre[v4] = v3;
        pre[v3] = v2;
        pre[v2] = v1;
    }

    // 出力
    print();
}