AtCoder が提供しているABC（AtCoder Beginner Contest）350 のC問題をC++とPythonで解いてみました。ABC350は、2024年4月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Sort（Difficulty : 394）
問題はリンク先をご覧ください。
ある数字がどこにあるか覚えておくことにより高速にソートします。AtCoder Problems による Difficulty は 394 でした。
解答案
C++ プログラム例（ABC350C）
数列を配列 a[i] に格納しながら、配列 n2index に数字がどこに格納されているか記憶しておきます。なお、配列の添え字に合わせるために、数列の値は0からカウントしています（12行目）。
数列の i 番目に i が無ければ、i がある場所を n2index で調べて、もとの配列 a[i] と合わせて更新します（20ー23行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> n2index(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
--a[i];
n2index[a[i]] = i;
}
vector<pair<int, int>> result;
for (int i = 0; i < n; ++i) {
if (a[i] != i) {
int t = n2index[i];
n2index[a[i]] = t;
n2index[i] = i;
a[t] = a[i];
a[i] = i;
result.push_back(make_pair(i + 1, t + 1));
}
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
cout << result[i].first << " " << result[i].second << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC350C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 350 C"""
n = int(input())
a = list(map(int, input().split()))
n2index = [0] * n
for i in range(n):
a[i] -= 1
n2index[a[i]] = i
result = []
for i in range(n):
if a[i] != i:
t = n2index[i]
n2index[a[i]] = t
n2index[i] = i
a[t] = a[i]
a[i] = i
result.append((i + 1, t + 1))
print(len(result))
for i in range(len(result)):
print(*result[i])こちらも「AC」と判定されました。
最後に
計数ソートと同じ考え方で解くことができました。範囲が小さい場合に使える手法です。
引き続き ABC の問題を紹介していきます。
