実はアルゴ式でもよく似た問題をすでに出していました!
問題概要
がこの順に並んでいます。この数列に対して 回のクエリが投げられました。
各クエリでは、値 が指定されて、次の操作を実行します。
数列中の整数 に対し、その右隣の要素が存在するならば、その要素と swap する。存在しないならば左隣の要素と swap する
回の操作を終えたあとの数列を求めてください。
制約
考察
最初の注意点として、問題文は というように 1 始まりとなっていますが、ここでは というように 0 始まりで考えます。与えられるクエリ も 1 を引いて考えます。
さて、この問題の難しいところは「クエリが与えられたときに、整数値 がどこにあるのかが分からなくなる」ことです。
その場合に最もよく採られる解決方法は、次のように「要素がどこにあるか」を表すデータ構造を用意することです!!!
pos[v]
← 数列 val
において、要素 v
が何番目の要素であるか
このデータは、とくに数列 val
が順列であるとき逆順列と呼びます。たとえば val
のとき、逆順列は pos
です。
- 0 は 2 番目の要素です
- 1 は 0 番目の要素です
- 2 は 1 番目の要素です
このように逆順列も合わせて考えることで、この問題は解けます。なお、連結リストを用いる別解もあるので、それも後述します。
解法 (1):逆順列も管理する
順列を val
、逆順列を pos
と表すことにしましょう。そうすれば、次のように考えられます。
- 値
v
の位置p
をp = pos[v]
によって取得できる - 位置
p
の右隣の位置をp2 = p + 1
とする (右端の場合はp2 = p - 1
) swap(val[p], val[p2])
を実行する
ただしこのとき、逆順列の方も更新が必要であることに注意しましょう。次のようにします。
- 位置
p2
の要素の値v2 = val[p2]
を取得する swap(pos[v], pos[v2])
を実行する
これらの作業は で実行できますので、クエリ全体に要する計算時間は となります。
最初に入力を受け取ったり、配列 pos
を初期化したりする処理も合わせて、全体の計算量は となります。
コード
#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; }
別解:連結リスト
技術的な詳しい話については、アルゴ式の一連の問題集を参考にしてください。
要素をつなぎ変えたり、削除したり (今回は削除は不要) する処理は、連結リストを用いて容易に表現できます (→ 類題たち)。今回は具体的には次の 2 つのデータを用意しましょう。
nex[v]
← 要素v
の次の要素は何か (存在しないなら -1)bak[v]
← 要素v
の前の要素は何か (存在しないなら -1)
これらのデータを逐次更新していきます。計算量はやはり となります。
#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(); }