AtCoder Beginner Contest 171 D問題

AtCoder Python

D問題

難易度：茶色

10~12分で解けました。

並べられた整数列Aに対して
Biの整数に該当する要素を全てCiに置き換え、
最終的な合計値を求めます。

整数列の要素数やBiの個数が100000個存在します。
そのため二重ループするとTLEとなる確率が高い。

よってcollections.Counterで、
各整数ごとに頻出回数をまとめたリスト'a'を作成します。。

「Biに該当する整数の数」と「新たに変換するCiと変換前のBiの差分」の積をとります。
これを合計値に反映させ、
整数頻出リスト'a'を更新します。

以下のコードはACです。

import collections
 
n = int(input())
A = list(map(int,input().split()))
a = collections.Counter(A)
sum_ = sum(A)
 
Q = int(input())
B,C = [],[]
for i in range(Q):
  lis = list(map(int,input().split()))
  B.append(lis[0])
  C.append(lis[1])
 
for j,b in enumerate(B):
  sum_+=a[b]*(C[j]-b)
  a[C[j]]+=a[b]
  a[b]=0
  print(sum_)