AtCoderBeginnerContest171復習＆まとめ（後半）

AtCoder ABC171

2020-06-21(日)に行われたAtCoderBeginnerContest171の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．前半はこちら．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

D問題　Replacing

問題文
あなたは、$N$個の正整数$A_1,A_2,⋯,A_N$からなる数列$A$を持っています。
あなたは、これから以下の操作を$Q$回、続けて行います。
　・$i$回目の操作では、値が$B_i$である要素すべてを$C_i$に置き換えます。
すべての$i(1 \leq i \leq Q)$に対して、$i$回目の操作が行われた後の数列$A$のすべての要素の和、$S_i$を求めてください。

毎回，和の計算をしていると時間が足りなくなってしまうと思ったので，操作ごとに差分を計算するようにしました．
数列$A$はdictで管理するようにしました．

abc171d.py

n = int(input())
a_list = list(map(int, input().split()))
a_dict = {}
total = 0
for a in a_list:
    if a in a_dict:
        a_dict[a] += 1
    else:
        a_dict[a] = 1
    total += a

q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    if b in a_dict:
        if c in a_dict:
            a_dict[c] += a_dict[b]
        else:
            a_dict[c] = a_dict[b]
        total -= a_dict[b] * b
        total += a_dict[b] * c
        a_dict[b] = 0
    print(total)

D問題までは順調に解けました．
しかし，次のE問題に躓き解けませんでした．

E問題　Red Scarf

問題文
猫のすぬけくんが$N$(偶数)匹います。
各すぬけくんには$1,2,…,N$の番号が振られています。
各すぬけくんは首に赤いスカーフを巻いており、スカーフにはそのすぬけくんが一番好きな非負整数が$1$つ書き込まれています。
すぬけくんたちは最近、整数の xor（排他的論理和）と呼ばれる演算を覚えました。
早速この演算を使いたくなったすぬけくんたちは、自分以外のすぬけくんのスカーフに書かれた整数の xor を計算することにしました。
番号$i$が振られたすぬけくんが計算した、自分以外のすぬけくんのスカーフに書かれた整数の xor が$a_i$であることが分かっています。 この情報を元に、各すぬけくんのスカーフに書かれた整数を特定してください。

4264人もE問題が解けてて，D解けた段階で2000位くらいだったのに，最終的に順位が目も当てられない結果になってしまいました．
偶数がポイントになってたんですね．
自分もノートにいろいろ式を計算したりしてみたのですが，答えを求めるための式を出せませんでした．
次はもう解けると思うので，勉強になったと割り切りたいと思います．

abc171e.py

n = int(input())
a_list = list(map(int, input().split()))
y = 0
for a in a_list:
    y = y ^ a
for a in a_list:
    x = y ^ a
    print(x, end=" ")

F問題は，今週も忙しいので時間ができたときにでも追記できたらいいなと思ってます．

後半も最後まで読んでいただきありがとうございました．