ABC343 D問題の解説（Python）

はじめに

この記事では、ABC343のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC343　D – Diversity of Scores

問題

問題

1からNまでの番号が付けられたN人の選手がコンテストに参加しています。

i = 1, 2, …, T について、今から i 秒後に選手 \(A_i\) の得点が \(B_i\) 点増加することが分かっています。

各時刻に対し、N人の選手のその時刻における得点に何種類の値が現れるかを求める問題です。

例えば、ある時刻において選手たちの得点がそれぞれ10, 20, 30, 20点であった場合、この時刻での選手たちの得点には3種類の値が現れています。

制約

• \(1 \leqq N,T \leqq 2×10^5\)
• \(1 \leqq A_i \leqq N\)
• \(1 \leqq B_i \leqq 10^9\)

思考の筋道

各得点の人が何人いるかを管理しましょう。

はじめの段階では0点の人がN人です。1人が10点を得たとすると、0点の人がN-1人となり、10点の人が1人になります。このように人数の変動を管理していきましょう。管理には、辞書（keyが点数、valueがその点数の人数）を使えばよいです。

辞書のキーの数がその時刻における得点の種類数です。

コード

N, T = map(int, input().split())

P = [0] * N
d = {0: N}

for _ in range(T):
    A, B = map(int, input().split())

    d[P[A - 1]] -= 1
    if d[P[A - 1]] == 0:
        del d[P[A - 1]]

    P[A - 1] += B

    if P[A - 1] not in d.keys():
        d[P[A - 1]] = 1
    else:
        d[P[A - 1]] += 1

    print(len(d.keys()))

以上、ABC343のD問題の解説でした！

では、またね。

リンク