AtCoder が提供しているABC（AtCoder Beginner Contest）279 のE問題をC++とPythonで解いてみました。ABC279は、2022年11月26日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Cheating Amidakuji（Difficulty : 1390）
問題はリンク先をご覧ください。
前からの結果を先に求めてから、後ろからのあみだくじを組み合わせます。AtCoder Problems による Difficulty は、1390 でした。
解答案
1 から $N$ までの選択肢があり、$M$ 本の横棒があるあみだくじを考えます。$i$ 本目の横棒を抜いたときに、1 が行く先を出力する問題です。
- 前から 1 がどこに移るのか、求めておきます。
- 後ろからのあみだくじを求めておいた、前からの結果と組み合わせます。
C++ プログラム例（ABC279E）
以下は、プログラムの補足です。
- 配列 pre に、1 の行く先を格納します（13ー23行目）。
- 配列 post には、後ろから考えたあみだくじを格納します。初期値は、post[i] = i となります（25ー28行目）。
- 後ろから考えたあみだくじに、前から求めた結果をあわせます（31行目）。
- あみだくじを更新します（32ー34行目）。
- 配列 result は、逆に格納されているため、反転して出力します（37ー40行目）。
プログラムは、以下となります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i];
}
vector<int> pre(m);
pre[0] = 1;
for (int i = 0; i < m - 1; ++i) {
if (pre[i] == a[i]) {
pre[i + 1] = pre[i] + 1;
} else if (pre[i] == a[i] + 1) {
pre[i + 1] = pre[i] - 1;
} else {
pre[i + 1] = pre[i];
}
}
vector<int> post(n + 1);
for (int i = 1; i <= n; ++i) {
post[i] = i;
}
vector<int> result;
for (int i = m - 1; i >= 0; --i) {
result.push_back(post[pre[i]]);
int t = post[a[i]];
post[a[i]] = post[a[i] + 1];
post[a[i] + 1] = t;
}
reverse(result.begin(), result.end());
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << endl;
}
return 0;
}このプログラムは、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC279E）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 279 E"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
pre = [0] * m
pre[0] = 1
for i in range(m - 1):
if pre[i] == a[i]:
pre[i + 1] = pre[i] + 1
elif pre[i] == a[i] + 1:
pre[i + 1] = pre[i] - 1
else:
pre[i + 1] = pre[i]
post = [0] * (n + 1)
for i in range(1, n + 1):
post[i] = i
result = []
for i in range(m - 1, -1, -1):
result.append(post[pre[i]])
post[a[i]], post[a[i] + 1] = post[a[i] + 1], post[a[i]]
result.reverse()
print(*result, sep='\n')このプログラムも「AC」と判定されました。
最後に
当時、ABC279 はD問題まで解けました。E問題は問題を読んであきらめました。前に解けなかった問題を、実力向上のため解いています。
引き続き ABC の問題を紹介していきます。
