けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 171 E - Red Scarf (500 点)

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

問題へのリンク

問題概要

 N を偶数とする。 N 個の 0 以上の整数  x_{1}, x_{2}, \dots, x_{N} であって、以下の条件を満たすものを求めよ。

  •  N 個の整数のうち  i 番目を除外した  N-1 個の整数の XOR 和が  A_{i} となる

制約

  •  2 \le N \le 2 \times 10^{5}

考えたこと

 N が偶数というのが不気味だけど、とりあえず  N = 4 の場合について考えてみる。このとき、条件は次のような方程式になる。ただし、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

で求められる。計算量は  O(N)。なお、「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 になってしまうのだ。