AtCoder

ABC298 C問題(Cards Query Problem)を解く

AtCoder_ABC298_C

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問しか解くことができませんでしたが、D問題以降も可能な範囲で解説します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA