ABC306 C問題（Centers）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）306 のC問題をC++とPythonで解いてみました。ABC306は、2023年6月17日21:00に実施されました。

この回は、コンテスト中にジャッジ遅れが大きく発生したため、unrated となりました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Centers（Difficulty : 159）

問題はリンク先をご覧ください。

ABC306 C問題 Centers

バケットと呼ばれる入れ物を使って問題を解きます。AtCoder Problems による Difficulty は 159 でした。

解答案

この問題を解くためにそれぞれの数字の出現頻度をカウントします。出現頻度を格納する入れ物をバケットと呼びます。

C++ プログラム例（ABC306C）

バケットを map で実現します。2回目に表れた数を配列 result に格納していきます。最後に result を出力します。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(3 * n);
	for (int i = 0; i < 3 * n; ++i) {
		cin >> a[i];
	}

	map<int, int> m;
	vector<int> result;
	for (int i = 0; i < 3 * n; ++i) {
		++m[a[i]];
		if (m[a[i]] == 2) {
			result.push_back(a[i]);
		}
	}

	for (int i = 0; i < result.size(); ++i) {
		cout << result[i] << " \n"[i == result.size() - 1];
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC306C）

Python では、バケットとして defaultdict を使います。考え方は、C++ と同じです。

"""AtCoder Beginner Contest 306 C"""
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

m = defaultdict(int)
result = []
for i in range(3 * n):
    m[a[i]] += 1
    if m[a[i]] == 2:
        result.append(a[i])

print(*result)

こちらも「AC」と判定されました。

最後に

バケットは対象となる数字の種類が少なければ配列が使えます。対象となる数字の範囲が大きければ連想配列を使うことになります。

わたしは、バケットは基本的に連想配列を使っています。もっと慣れてくれば、対象により使い分けるかもしれません。

引き続き ABC の問題を紹介していきます。