ABC343 D問題（Diversity of Scores）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）343 のD問題をC++とPythonで解いてみました。ABC343は、2024年3月2日21:00に実施されました。

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

D問題 Diversity of Scores（Difficulty : 422）

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

ABC343 D問題 Diversity of Scores

それぞれの得点を持つひとの人数をmapコンテナで管理します。AtCoder Problems による Difficulty は 422 でした。

解答案

それぞれの得点をもつ人数をmapコンテナpointで管理します。初期値は、point[0] = N となります。一組の（選手A_i、得点B_i）を読み出して以下を行います。

• 元の Ai の得点の人数をひとつ減らす。
  • もし、人数が0になれば、mapコンテナから、その得点をキーとする要素を削除する。
• A_i の得点に B_i を加えて、この得点を持つ人数をひとつ増やす。

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

それぞれの選手の得点を配列 p、得点分布をmapコンテナpointで管理します。上で考察したように、元の値の得点を持つ人をひとつ減らした場合に0になるようなら、mapコンテナの要素の削除が必要になります（22行目）。

得点分布を更新した後に、pointのsizeを出力します（27行目）。

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

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

typedef unsigned long long int ull;

int main()
{
	int n, t;
	cin >> n >> t;
	vector<ull> p(n, 0);
	map<ull, int> point;
	point[0] = n;

	for (int i = 0; i < t; ++i) {
		int a;
		ull b;
		cin >> a >> b;
		--a;
		ull old = p[a];
		p[a] += b;
		if (point[old] == 1) {
			point.erase(old);
		} else {
			--point[old];
		}
		++point[p[a]];
		cout << point.size() << endl;
	}

	return 0;
}

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

Python プログラム例（ABC343D）

Python 版も基本的な考え方は同じです。得点の分布を defaultdict で管理します。以下となります。

"""AtCoder Beginner Contest 343 D"""
from collections import defaultdict

n, t = map(int, input().split())
p = [0] * n
point = defaultdict(int)
point[0] = n

for i in range(t):
    a, b = map(int, input().split())
    a -= 1
    old = p[a]
    p[a] += b
    if point[old] == 1:
        del point[old]
    else:
        point[old] -= 1
    point[p[a]] += 1
    print(len(point))

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

最後に

今回のコンテストは、このD問題までは取り組みやすく、これ以降のE問題（Difficulty 1802）、F問題（Difficulty 1370）と難易度に差がありました。

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