【ABC171 D】「Replacing」を解く【Python3】

コンテスト一覧へ

 

N個の正整数からなる数列Aに対して、特定の操作をQ回行い、i回目の操作が行われたあとのSiをすべて求める問題です。

提出
import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())

bc = []

for i in range(q):
    bci = list(map(int, input().split()))
    bc.append(bci)

d = collections.Counter(a)
ans = sum(a)

for i in range(q):
    b, c = bc[i]
    num = (c-b)*d[b]
    ans += num
    print(ans)
    d[c] += d[b]
    d[b] = 0

入力はすべて整数です。

collectionsモジュールのCounter()を用いることで、リスト内の要素の個数を数えることができます。

l = [1, 1, 1, 1, 2, 3, 3]
c = collections.Counter(l)
print(c)                        
# > Counter({1: 4, 3: 2, 2: 1})

 

今回の問題では、まず、リストAの合計値を求めておきます。

毎回リストの合計値を求めては時間コストがかかるので、この最初の合計値と置換した数字を使って、要素の和を計算します。

Counter()は、辞書型として扱うことができ、キーを指定することで、値が返ってきます。

置き換えた後(=c)の数字から置き換える前(=b)の数字を引き、個数(=d[b])を掛けたものが差分になるため、「ans」にこれを足していきます。

「ans」を出力し、cの個数を増やし、bの個数を0と処理して、ループを続けます。

【ABC171】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。