AtCoder が提供しているABC（AtCoder Beginner Contest）298 のC問題をC++とPythonで解いてみました。ABC298は、2023年4月15日21:00に実施されました。
この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Cards Query Problem（Difficulty : 548）
問題はリンク先をご覧ください。
ABC298 C問題 Cards Query Problem
コンテナを使ってクエリに答える問題です。AtCoder Problems による Difficulty は 548 でした。
解答案
C++ プログラム例（ABC298C）
箱に入っているカードの数字は、重複を許すため multiset を使います。一方、数が入っている箱は、重複を許さないため set を使います。multiset も set も内部は、二分探索木で管理されているため、デフォルトでは昇順に $O(\log N)$ の計算量で値を取り出せます。
それぞれのコンテナは、map で番号と紐づけました（9、10行目）。ただし vector で番号と紐づけた方が速いです。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
map<int, multiset<int>> boxes;
map<int, set<int>> cards;
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 1) {
int i, j;
cin >> i >> j;
boxes[j].insert(i);
cards[i].insert(j);
} else if (command == 2) {
int i;
cin >> i;
for (auto e : boxes[i]) {
cout << e << " ";
}
cout << endl;
} else if (command == 3) {
int i;
cin >> i;
for (auto e : cards[i]) {
cout << e << " ";
}
cout << endl;
}
}
return 0;
}AtCoder の要素を出力する場合、「空白区切りで出力し」とあります。改行の前に空白が入っても許されるようです。サイトの方針によっては、改行の前の空白を許さない場合があるかもしれません（AOJのいくつかの問題では、改行前の空白を許しません）。
AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC298C）
Python 版は、list と set を使いました。defaultdict で紐づけています（7、8行目）。Python では、それぞれの要素が昇順に取り出せるわけではありません。sort した結果を出力しています（17、20行目）。
"""AtCoder Beginner Contest 298 C"""
from collections import defaultdict
n = int(input())
q = int(input())
boxes = defaultdict(list)
cards = defaultdict(set)
for _ in range(q):
q = list(map(int, input().split()))
if q[0] == 1:
i, j = q[1], q[2]
boxes[j].append(i)
cards[i].add(j)
elif q[0] == 2:
i = q[1]
print(*sorted(boxes[i]))
elif q[0] == 3:
i = q[1]
print(*sorted(cards[i]))こちらも「AC」と判定されました。
最後に
この問題は、AC を取ることができましたが、途中で問題を誤読して時間を取られました。B問題とC問題で、どちらも問題を正しく読めずに時間を取られてしまいました。結果的に今回は3問しか解くことができませんでした。
引き続き ABC の問題を紹介していきます。
