Help us understand the problem. What is going on with this article?

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問題は,今週も忙しいので時間ができたときにでも追記できたらいいなと思ってます.

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

takaito0423
Qiitaでは,競プロに出た問題を復習するために記事書いたり,これからプログラミン始めたりする人のために,記事を投稿していく予定です. 基本的に難しいことよくわからないですが,学習意欲はあるので,優しくアドバイスコメントもらえるととても嬉しいです. よろしくお願いいたします.
http://hawk.ci.seikei.ac.jp/kaito/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away