ABC171 E - Red Scarf

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    all = A[0]
    for n in range(1, N):
        all ^= A[n]

    ret = []
    for n in range(N):
        ret.append(A[n] ^ all)
    print(*ret)


if __name__ == '__main__':
    main()

考え方

与えられる整数列をA1, A2, ... ,An、回答の整数列をB1, B2, ..., Bnとしたとき、
与えられた整数列を全てxorした値SからA1をxorするとB1になる。

詳しくは公式解説と競技プログラミングをするフレンズ氏(@kyopro_friends)のツイートが参考になる。
公式解説

アライグマ「E問題は、答えをXiとするとAiを全部XORした結果SにはXiがN-1回ずつ入ってるのだ。だからS XOR Aiが答えになるのだ！　「『自分以外の合計』がわかってるときは、それを全部足すと合計のN-1倍になる」っていうのは前にもどっかで見たことがあるのだ！」 pic.twitter.com/3eN3WF0gkc

— 競技プログラミングをするフレンズ (@kyopro_friends) June 21, 2020

整数は必ず偶数個与えられる。そのため、与えられた整数列を全てxorした値Sと
A1をxorすると、B2, B3, ... Bnの数が偶数個になり、B1のみが残る。

A1 ^ S = B1

あとは全てのA1, A2, ..., Anに対して、Sとのxorを求めれば回答を得られる。