AtCoder ABC 171 E - Red Scarf (茶色, 500 点)

XOR について完全理解することが求められる...！

問題へのリンク

問題概要

を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。

• 個の整数のうち 番目を除外した 個の整数の XOR 和が となる

制約

• 

考えたこと

が偶数というのが不気味だけど、とりあえず の場合について考えてみる。このとき、条件は次のような方程式になる。ただし、XOR を「 ^ 」で表している。

     x2 ^ x3 ^ x4 = A1
x1      ^ x3 ^ x4 = A2
x1 ^ x2      ^ x4 = A3
x1 ^ x2 ^ x3      = A4

こういう対称な方程式を見たら、とりあえず式全部を足してみたくなる！全部足すと、左辺は、

• x1 が 3 個
• x2 が 3 個
• x3 が 3 個
• x4 が 3 個

という感じになっている。ここで、XOR 和の性質を思い出そう。XOR 和は、以下のように、偶数個だと 0 になり、奇数個だと 1 個分になる、という性質がある。

• a ^ a = 0
• a ^ a ^ a = a
• a ^ a ^ a ^ a = 0
• a ^ a ^ a ^ a ^ a = a
• ...

よって、上の連立方程式を式を全部足すと、次のようになる。

x1 ^ x2 ^ x3 ^ x4 = B
(ただし B = A1 ^ A2 ^ A3 ^ A4 とした)

ここまで来たら

とても嬉しいことに、x1, x2, x3, x4 の XOR 和がわかったので、ノリとしては

• x1 ^ x2 ^ x3 ^ x4 = B

から

• x2 ^ x3 ^ x4 = A1

を "引く" というのをすると、x1 を求めることができそうな気がしてくる (同様に、x2, x3, x4 も求められる)。「引く」という行為が実現えきればよいことになるので、XOR 和において「引く」とはどういうことだろう...と疑問が湧いてくる。でも実は、XOR 和においては、「足す」も「引く」も一緒なのだ。試しに、

• x1 ^ x2 ^ x3 ^ x4 = B
• x2 ^ x3 ^ x4 = A1

を足してみよう。そうすると、x1 以外の x2, x3, x4 はそれぞれ 2 個ずつの XOR 和になるので、0 になって消えるのだ。よって、

• x1 = B ^ A1

となる。これで x1 が求められた。同様にして、

• x1 = B ^ A1
• x2 = B ^ A2
• x3 = B ^ A3
• x4 = B ^ A4

になるということもわかる。

一般の N でも

ここまで N = 4 で考えていたけど、一般の N でも一緒で

• B = A1 ^ A2 ^ ... ^ AN として
• x[ i ] = B ^ Ai

で求められる。計算量は 。なお、「N が偶数」という条件がどこに響いてくるのかについては、下の方で補足を。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    long long B = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        B ^= A[i];
    }
    for (int i = 0; i < N; ++i) cout << (B^A[i]) << endl;
}

おまけ: N が奇数だと...？？

N = 4 のときの連立方程式は

     x2 ^ x3 ^ x4 = A1
x1      ^ x3 ^ x4 = A2
x1 ^ x2      ^ x4 = A3
x1 ^ x2 ^ x3      = A4

という形だった。これを全部足すとき、x1, x2, x3, x4 がそれぞれ 3 個ある。これは一般には N-1 個ということになる。よって

• N が偶数だと、N - 1 は奇数なので、xi がそれぞれ奇数個なので、 XOR 和すると xi になる
• N が奇数だと、N - 1 は偶数なので、xi がそれぞれ偶数個なので、XOR 和をとると 0 になる

という風になる。N が奇数だと、各式を全部足したときに左辺が 0 になってしまうのだ。