AtCoder が提供しているABC（AtCoder Beginner Contest）344 のE問題をC++とPythonで解いてみました。ABC344は、2024年3月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Insert or Erase（Difficulty : 973）
問題はリンク先をご覧ください。
自前で双方向リンクを管理します。AtCoder Problems による Difficulty は 973 でした。
解答案
双方向リストの考え方を流用します。
- 与えられた数列 a に対して、以下の2つの連想配列を定義する。
- その値と、次の値を紐づける連想配列 post
- その値と、前の値を紐づける連想配列 pre
この二組の連想配列の値を処理することによって、値の挿入と削除ができます。
- 挿入）x → z の並びに対して、x の後ろに y を挿入します。
- 定義から、post(x)=z、pre(z)=x となっている。
- 次のように書き換えを行う。
- post(x)=y、post(y)=z、pre(z)=y、pre(y)=x
- 上記によって、x → y → z と挿入することができた。
- 削除）ｚ → ｘ → y の並びに対して、x を削除します。
- 定義から、post(z)=x、post(x)=y、pre(y)=x、pre(x)=z となっている。
- 次のように書き換えを行う。
- post(z)=y、pre(y)=z、post(x)とpre(x)は連想配列から削除する。
- 上記によって、z → ｙ となり、x を削除することができた。
C++ プログラム例（ABC344E）
上で説明した考え方をプログラムに変換しました。数列の門番として最初の要素を0、最後の要素を-1としました（※0とー1は数列の要素にならない）。この門番を設定することにより、与えられた数列のすべての要素に対して、post と pre が定義できます。
すべての値を走査するには、値 0 から始めて post をたどり、-1 が得られるまで繰り返します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n + 2);
a[0] = 0;
a[n + 1] = -1;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
map<int, int> post;
map<int, int> pre;
for (int i = 0; i <= n; ++i) {
post[a[i]] = a[i + 1];
pre[a[i + 1]] = a[i];
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
int x, y;
cin >> x >> y;
int z = post[x];
post[x] = y;
post[y] = z;
pre[z] = y;
pre[y] = x;
} else if (type == 2) {
int x;
cin >> x;
int z = pre[x];
int y = post[x];
post[z] = y;
pre[y] = z;
post.erase(x);
pre.erase(x);
}
}
int index = 0;
while (post[index] != -1) {
cout << post[index] << " ";
index = post[index];
}
cout << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC344E）
Python 版も基本的な考え方は同じです。map コンテナの替わりに辞書を使います。以下となります。
"""AtCoder Beginner Contest 344 E"""
n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(-1)
post = {}
pre = {}
for i in range(n + 1):
post[a[i]] = a[i + 1]
pre[a[i + 1]] = a[i]
q = int(input())
for _ in range(q):
query = list(map(int, input().split()))
t = query[0]
if t == 1:
x, y = query[1], query[2]
z = post[x]
post[x] = y
post[y] = z
pre[z] = y
pre[y] = x
elif t == 2:
x = query[1]
z = pre[x]
y = post[x]
post[z] = y
pre[y] = z
del post[x], pre[x]
result = []
index = 0
while post[index] != -1:
result.append(post[index])
index = post[index]
print(*result)こちらも「AC」と判定されました。
最後に
この問題を解くためにSTLのListを使うことを思いつきましたが、この問題は特定の値の場所に素早くアクセスできる必要（$O(N)$ では遅い）がありました。
STLのListはランダムアクセスができず、そこで思考が止まっていました。リスト構造の本質的な仕組みが分かっていれば解けていた問題でした。勉強になりました。
引き続き ABC の問題を紹介していきます。
