AtCoder Beginner Contest 171を見直す(その3）D問題 - Replacing

D - Replacing

D - Replacing

問題

N個の整数からなる数列Aが与えられるその数列に対して以下の処理をQ回行いQ毎の合計を算出する
・値がBiである要素の値を全てCiに置き換える

制約

1<=N,A,Q,Bi,Ci<=10^5

例

A:1,2,3,4に対してQ:（1, 2）,(2, 4)が与えられた場合
(1, 2)でA:2, 2, 3, 4となり、出力が11
(2, 4)でA:4, 4, 3, 4となり、出力が15

どう認識したか

とにかく、数が多いなんの工夫もしないと完全にアウト（TLE）なので何かしら工夫が必要。数列を実際に操作するのも、数列の合計を毎度出すのもアウトなので、元ある数列は書き換えない、先に合計を一度出してそこから変化した値だけ計算するようにしたい。と言うことで作成したのが以下の回答。

私の解答

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC_List = x = [list(map(int, input().split())) for i in range(Q)]
int_list = [0 for _ in range(10**5+1)]
sum = 0
for i in A:
   int_list[i] += 1
   sum += i

for B, C in BC_List:
   sum = sum + (C-B) * int_list[B]
   int_list[C] += int_list[B]
   int_list[B] = 0
   print(sum)

整数の数については、実際の数列は触らずに先に「int_list」に数列に含まれる整数を記録して、そちらを操作するようにしました。また、合計値に関しては以下の式を変形させて上記のようになっています。

sum = sum - (B * int_list[B]) + (C * int_list[B])

解説動画見てもほぼ同じやり方だったので、多分ポピュラーな解答方法だと思われます。

前回