AtCoder Beginner Contest 171 - D - Replacing / E - Red Scarf

スピード勝負だった。Fは結局解けない。。

数列が与えられ、特定の数列の値を別の値に書き換える操作を行う。操作ごとにすべての和を答える。

Dにしてはとても簡単。

初期段階での数列の和を取っておいたとき、 BをCに変化させたとき、Bがb個あったとすれば、(C - B) * bだけ和が増える。

Counterで個数を数えておきながらこの差分だけ計算すれば毎回O(1)の計算量で、和を求めることができる。

import collections

def solve(N, As, Q, BCs):
    counter = collections.Counter(As)
    current_sum = sum(As)
    ans = []
    for b, c in BCs:
        if b in counter:
            original = counter[b] * b
            to = counter[b] * c
            diff = to - original
            current_sum += diff
            if c not in counter:
                counter[c] = 0
            counter[c] += counter[b]
            del counter[b]
        ans.append(str(current_sum))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    Q = int(input())
    BCs = [tuple(map(int, input().split(" "))) for _ in range(Q)]

    print(solve(N, As, Q, BCs))

atcoder.jp

数列が与えられる。この数列はある別の数列を元に、自分のindex以外のすべての値のxorを取ったもの。元の数列を求める。数列の長さは偶数であることが保証される。

これE問題？C問題ぐらいだろう。。

まず、与えられた数列すべてのxorを取りKとする。このKは数列の長さをNとしたとき、元の数列の各値をN-1回ずつxorしたものと等しくなる。

Nが偶数であるため、N-1は奇数であり、Kにはすべての要素が奇数回ずつxorされて含まれていることになる。

ここに、最初の数列のある位置の値をもう一度xorすると、その位置の元の値だけが含まれていないため、元の位置の値が奇数回、それ以外が偶数回xorされることになる。

偶数回のxorは値が０になるため、奇数回の値が浮かび上がり、それがそのまま答えになる。

def solve(N, As):
    k = 0
    for a in As:
        k ^= a
    ans = []
    for a in As:
        ans.append(str(k ^ a))
    return " ".join(ans)

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))