ABC343_D問題その2

昨日の続き

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

# 各選手の得点を保持する辞書Cを初期化
C = {i: 0 for i in range(1, N+1)}

# 得点をキーとして、その得点を持つ選手の数を値とする辞書Mを初期化。一番最初は0点の人がN人いる。
M = {0: N}

for _ in range(T):
    A, B = map(int, input().split())
    now_score = C[A]
    update_score = now_score + B #Aさんの名前をkeyにして現在の得点を呼び出し、増加分(B)を追加する

#以下で辞書Mの更新

    M[now_score] -= 1 #Aさんの得点が変化した分、Aさんが持っていた得点のグループから削除する
    if M[now_score] == 0:
        del M[now_score]

    C[A] = update_score #得点の更新

    if update_score in M:
        M[update_score] += 1
    else:
        M[update_score] = 1
    
    print(len(M))

①set(scores.values())を使うアプローチ(昨日の解法):

集合に変換する時、全ての要素にアクセスする必要があるのでT、Nのが大きいほど計算量が増える。

②辞書Mを使うアプローチ:

変化量に着目するので、T、得点の種類が多いほど計算量が増える。

まとめ

T、得点の種類が極めて大きい数の場合、計算量は微差になるけど、
基本的に後者の方が効率的だよねって解釈しました。

計算量は、処理の仕組みを理解していないといけないみたいですね。
ちょっとまだ自分のレベルだと厳しそうですw
A~C問題を解く上で、計算結果だけを追うのではなく内部でどのような処理をしているのか考えるようにしたいと思います！