AtCoder Beginner Contest 171 E - Red Scarf (XORを使う問題)

珍しくE問題が解けたので簡単に解説を入れます。

https://atcoder.jp/contests/abc171/tasks/abc171_e

端的に言えば、自分以外の整数の xor が分かっている状態で、自分の数を求めろという問題です。

ポイントは、Nが偶数であるということです。XORの性質を知っていれば、制約でNが偶数であることに言及されている時点でピンとくるかもしれません。

XORの性質として自分自身とのXORは0になるというものがあります。つまり、偶数回登場する値のXORは常に0になります。

この性質を使うと、以下のように各整数を求められます。整数をniとします。

aiを求めるには、i!=jのすべてのnjのXORをとれば良いです。
なぜなら、i!=jのすべてのajのXORをとると、自分以外のnjは全て偶数回XORがとられて0に消し込まれる一方、niだけは奇数回XORがとられるので残るからです。

つまり、i=1の整数n1は、
n1 = a2 ^ a3 ^ ... ^ an
と求められるわけですが、残りのniを求めるにあたっては、i=2を例にとれば、
n2 = a1 ^ a3 ^ ... ^ an
となることから、
n2 = n1 ^ a1 ^ a2
とすれば求まることに注意します。

実装は以下の通りです。

import sys
sys.setrecursionlimit(10**6)

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

su = 0

for i in range(1, n):
    su ^= a[i]
    
ans = [su]

for i in range(n-1):
    su ^= a[i] ^ a[i+1]
    ans.append(su)
    
print(*ans)

以下、D問題までのPython ACコードです。

https://atcoder.jp/contests/abc171/tasks/abc171_a

import sys
sys.setrecursionlimit(10**6)

s = input()

s_low = s.lower()

if s == s_low:
    print('A')
else:
    print('a')

https://atcoder.jp/contests/abc171/tasks/abc171_b

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
p = list(map(int, input().split()))

p.sort()

print(sum(p[:k]))

https://atcoder.jp/contests/abc171/tasks/abc171_c

import sys
sys.setrecursionlimit(10**6)

n = int(input())

d = {(i-97+1)%26:chr(i) for i in range(97,97+26)}

l = []

while n > 0:
    tmp = n%26
    l.append(tmp)
    if tmp == 0:
        n = n//26-1
    else:
        n //= 26

ans = ''

for i in l[::-1]:
    ans += d[i]
    
print(ans)

https://atcoder.jp/contests/abc171/tasks/abc171_d

import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = list(map(int, input().split()))
q = int(input())
readline = sys.stdin.readline
BC = [[int(i) for i in readline().split()] for _ in range(q)]

d = {}
for a in A:
    d[a] = d.get(a, 0) + 1

ans = []
su = sum(A)

for b,c in BC:
    if b in d:
        su = su - b*d[b] + c*d[b]
        d[c] = d.get(c, 0) + d[b]
        d.pop(b)
        ans.append(su)
    else:
        ans.append(su)

print(*ans)

これまでのA-D問題を中心としたPythonコードは以下に入れています。

github.com