AtCoder が提供しているABC（AtCoder Beginner Contest）294 のC問題をC++とPythonで解いてみました。ABC294は、2023年3月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Merge Sequences（Difficulty : 127）
問題はリンク先をご覧ください。
2つの数列をマージして、ソートした結果の添え字を元の数列の数字に適用する問題です。AtCoder Problems による Difficulty は 127 でした。
解答案
問題を以下の方針で解きます。
- N、M と数列 A と数列 B を読み込む。
- 数列 A と数列 B のすべての要素を含む数列 C を生成する。
- 数列 C をソートする。
- 数列 C の値と添え字（要素の順番）を紐づける。
- 数列 C の紐づけを数列 A と数列 B の各要素に適用する。
C++ プログラム例（ABC294C）
数列 A と数列 B の要素を C に登録します。ソートした後に、map を使って、数字と要素の順番を紐づけます。その紐づけ情報を元の数列 A と数列 B の要素に適用します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
vector<int> c;
for (int i = 0; i < n; ++i) {
cin >> a[i];
c.push_back(a[i]);
}
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
c.push_back(b[i]);
}
sort(c.begin(), c.end());
map<int, int> temp;
for (int i = 0; i < n + m; ++i) {
temp[c[i]] = i + 1;
}
for (int i = 0; i < n; ++i) {
cout << temp[a[i]] << " \n"[i == n - 1];
}
for (int i = 0; i < m; ++i) {
cout << temp[b[i]] << " \n"[i == m - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC294C）
Python では、C++ の map の代わりに辞書を使います。辞書の内容を元の数列 A と数列 B に適用して、それぞれの数列を表示しています（11-12行目および14-15行目）。
"""AtCoder Beginner Contest 294 C"""
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = a + b
c = sorted(c)
temp = {}
for i in range(n + m):
temp[c[i]] = i + 1
a = [temp[i] for i in a]
b = [temp[i] for i in b]
print(*a)
print(*b)こちらも「AC」と判定されました。
最後に
紐づけを map や辞書を使ってプログラムしました。よく使う手法なので、慣れておきたいです。
引き続き ABC の問題を紹介していきます。
