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

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

2018 codeFlyer 本選 D - 数列 XOR (600 点)

本番、最後には綺麗な解法になったけど、何度も WA を出して大変だったん。

問題へのリンク

問題概要

 N 要素の数列  A_1, A_2, \dots, A_N が与えられる。この数列に以下の操作を好きな回数だけ繰り返して数列  B_1, B_2, \dots, B_N にできるかどうかを判定せよ。

【操作】
 A_i A_i xor  A_{i+1} に置き換えるか、 A_{i+1} A_i xor  A_{i+1} に置き換えるかのいずれかを行う。

制約

  •  1 \le N \le 10^{5}
  •  0 \le A_{i}, B_{i} \le 2^{60}-1

考えたこと

XOR 操作に関する問題。まずはサンプル確認しつつ様相を掴む。

  •  A_i = A_{i} xor  A_{i+1} だけでなく  A_{i} =  A_{i} xor  A_{i+2} もできそう (他に影響残さずに)
  • もっとすごく頑張れば  A_{i} = A_{i} xor  A_{i+3} もできそうだし、一般に  A_{i} = A_{i} xor  A_{i+k} (他に影響残さずに)

という感じのことをひたすら考えていた。それより先に「隣り合う二項の swap」ができることを発見すると感銘である。 a b とが隣り合っているとき、

 a b

 a xor  b b

 a xor  b a (左から右へ)

 b a (右から左へ)

こうして、隣り合う  a b とが swap できることがわかった。隣り合う 2 数が swap できるということは、任意の 2 つが swap できるし、任意の並び替えができる。

というわけで、上で予想した通りの  A_{i} = A_{i} xor  A_{i+k} もできる。一旦  A_{i} A_{i+k-1} とを入れ替えておいて、 A_{i+k} を xor して、もう一度元に戻せば良い。

さて、以上の操作というのは実は「行列の掃き出し法」のような感じになっている。各  A_i を二進法で表してそれを 0-1 ベクトル (横ベクトル) だと思うと、数列  A_1, A_2, \dots, A_N は、 N × 60 の行列 ( A とする) になる。この視点で、上の結果を整理すると、問題の操作は

  •  A i 行目と  j 行目とを交換する
  •  A j 行目を  i 行目に (XOR の意味で) 加算する

ができるということになる。これは  A の各要素を 0, 1 のみの数とみたときの掃き出し法に他ならない。

そして掃き出し法の重要な性質として「掃き出し操作の逆の操作もまた、掃き出し操作である」というのがある。つまり、

  •  A に操作をほどこして  B にできるか

という問題の代わりに

  •  A にも  B にも操作をほどこして一致させられるか

という問題を考えても一緒である (この考え方は超頻出のイメージ)。ここで行列の掃き出し法 (行基本変形) には

  • 行基本変形を繰り返して得られる行基本変形標準形というのがあり、それは操作の順番に依らずに一意に定まる

という著しい特徴がある (このページの「行列の標準形」の節参照)。よって、 A B行基本変形標準形まで変形して、両者が一致するかを見れば良い。

WA 出しまくった理由

最初は、数列  A_1, A_2, \dots, A_N に操作を繰り返して、数列  B_1, B_2, \dots, B_N の各要素ごとに作れるかどうかをそれぞれ判定して、すべて作れればよいのだと勘違いしていた。

#include <iostream>
#include <vector>
using namespace std;

void Gauss(vector<long long> &A) {
  int rank = 0;
  for (int d = 0; d < 60; ++d) {
    int pivot = -1;
    for (int i = rank; i < (int)A.size(); ++i) {
      if (A[i] & (1LL<<d)) {
        pivot = i;
        break;
      }
    }
    if (pivot == -1) continue;
    swap(A[rank], A[pivot]);
    for (int j = 0; j < (int)A.size(); ++j) {
      if (j == rank) continue;
      if (!(A[j] & (1LL<<d))) continue;
      A[j] ^= A[rank];
    }
    ++rank;
  }
}

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

  Gauss(A);
  Gauss(B);
  if (A == B) puts("Yes");
  else puts("No");
}