AtCoder が提供しているABC（AtCoder Beginner Contest）366 C問題をC++とPythonで解いてみました。ABC366は、2024年8月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Balls and Bag Query（Difficulty : 180）
問題の詳細は、リンク先をご覧ください。
ABC366 C問題 Balls and Bag Query
整数の個数と整数の種類をそれぞれ管理します。AtCoder Problems による Difficulty は 180 でした。
解答案
それぞれの整数がいくつあるかを配列で管理します。この配列をバケットと呼ぶこともあるようです。
- 整数 $x$ の個数を増やす前の個数が $0$ であれば、整数の種類を増やします。
- 整数 $x$ の個数を減らして個数が $0$ になれば、整数の種類を減らします。
C++ プログラム例（ABC366C）
上の考察をそのままプログラムにしました。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int q;
cin >> q;
vector<int> v(1000001, 0);
int result = 0;
for (int i = 0; i < q; ++i) {
int type;
cin >> type;
if (type == 1) {
int x;
cin >> x;
if (v[x] == 0) {
++result;
}
++v[x];
} else if (type == 2) {
int x;
cin >> x;
--v[x];
if (v[x] == 0) {
--result;
}
} else if (type == 3) {
cout << result << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC366C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 366 C"""
q = int(input())
v = [0] * (10 ** 6 + 1)
result = 0
for i in range(q):
query = list(map(int, input().split()))
t = query[0]
if t == 1:
x = query[1]
if v[x] == 0:
result += 1
v[x] += 1
elif t == 2:
x = query[1]
v[x] -= 1
if v[x] == 0:
result -= 1
elif t == 3:
print(result)こちらも「AC」と判定されました。
最後に
クエリを処理する問題としては、もっとも取り組みやすい難易度でした。
引き続き ABC の問題を紹介していきます。
