AtCoder が提供しているABC（AtCoder Beginner Contest）295 のC問題をC++とPythonで解いてみました。ABC295は、2023年3月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Socks（Difficulty : 122）
問題はリンク先をご覧ください。
バケットを使う典型的な問題です。AtCoder Problems による Difficulty は 122 でした。
解答案
出現するデータの頻度をカウントするために、あらかじめ用意した容器（バケット）に頻度を格納していく手法は、競技プログラミングでは、よく使われています。
この問題であれば、靴下の色の頻度をバケットでカウントして、2で割り切り捨てた商の合計が解答となります。
C++ プログラム例（ABC295C）
バケットは配列を使うこともありますが、わたしは map を使うことがほとんどです。今回も map を用いて靴下の色の出現頻度をカウントしました。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
map<int, int> a;
for (int i = 0; i < n; ++i) {
int t;
cin >> t;
++a[t];
}
int result = 0;
for (auto e : a) {
result += e.second / 2;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC295C）
Python は、defaultdict を使いました。基本的に C++ のプログラムを移植しただけです。
"""AtCoder Beginner Contest 295 C"""
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
m = defaultdict(int)
for i in range(n):
m[a[i]] += 1
result = 0
for v in m.values():
result += v // 2
print(result)こちらも「AC」と判定されました。
最後に
バケットを使う典型問題でした。このため、B問題（156）とDifficultyが逆転しました。このような問題は、速く解くことが求められると考えています。
引き続き ABC の問題を紹介していきます。
