ABC解説

ABC343 D問題の解説（Python）

はじめに

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

今回はABC343のD問題を解説していきます。

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がその点数の人数）を使えばよいです。

選手 \(A_i\) の得点が \(B_i\) 点増加したときの管理
  1. 選手 \(A_i\) の得点にあたる人数を1人減らす。
    その際、人数が1人から0人に減った得点は辞書から削除する。
  2. 選手 \(A_i\) の得点を \(B_i\) 点増やす。
  3. 選手 \(A_i\) の増加後の得点にあたる人数を1人増やす。
    その際、人数が0人から1人に増えた得点は辞書に追加する。

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

コード

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