XORゲームの結果が0になるかどうかを判定するC++プログラム

N個の要素を持つ配列Aと、長さNの2進文字列Sが与えられているとします。ここで、番号0と番号1の2人のプレイヤーがゲームを行います。変数xの初期値は0で、ゲームは全部でNラウンド構成されています。i回目のラウンドでは、S[i]に対応するプレイヤーが「xを x XOR A[i] に置き換える」か「何もしない」のいずれかを選択します。プレイヤー0はゲーム終了時にxが0になることを望み、一方プレイヤー1は0以外になることを望みます。私たちの課題は、ゲーム終了時にxが0になるかどうかを判定することです。

例えば、入力が A = [1, 2]、S = "10" の場合、出力は 1 になります。これは、プレイヤー1が x を 0 XOR 1 = 1 に更新するため、プレイヤー0がどのような選択をしても x は必ず 1 のままとなり、0にならないからです。

解法の考え方

この問題は、XOR演算の性質を活かした「線形基底（掃き出し法）」というテクニックを使うと効率的に解けます。配列Aを後ろから順に走査し、各値をサイズ60の配列judge（基底）へ登録していきます。すでに登録済みの値とのXORを繰り返して値を簡約し、最終的に0になればその値は既存の基底で表現できる（従属している）ことを意味し、0にならなければ新しい基底としてjudgeに格納します。

重要なポイントは、プレイヤー1が担当するラウンド（S[n]が'0'以外）において、そのラウンドの値A[n]が後続の要素から独立している（＝新しい基底として追加できた）ケースです。このときプレイヤー1は「A[n]を使うか使わないか」を選べるため、後続のプレイヤー0がどう対抗しても最終的なxを0以外に保てます。したがって、このような状況が一度でも発生すれば答えは1（xは0にならない）、一度も発生しなければ答えは0（xは0にできる）となります。

手順

この問題を解くために、以下の手順に従います。

N := Aのサイズ
サイズ60の配列judgeを定義
z := 0
judgeをすべて0で初期化
n := N - 1 から 0 まで（nを1ずつ減らしながら）繰り返す：
    x := A[n]
    以下を無条件に繰り返す：
        x が 0 と等しい場合：
            ループを抜ける
        y := x
        I := -1
        i := 0 から 60 未満まで（iを1ずつ増やしながら）繰り返す：
            y mod 2 が 1 の場合：
                I := i
            y := y / 2
        judge[I] が 0 の場合：
            judge[I] := x
            ループを抜ける
        x := x XOR judge[I]
    S[n] が '0' と等しくない場合：
        x が 0 と等しくない場合：
            z := 1
zを返す

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

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

int solve(vector<int> A, string S){
   int N = A.size();
   int judge[60];
   int z = 0;
   fill(judge, judge + 60, 0);
   for (int n = N - 1; 0 <= n; n--){
      int x = A[n];
      while (1){
         if (x == 0)
            break;
         int y = x;
         int I = -1;
         for (int i = 0; i < 60; i++){
            if (y % 2 == 1)
               I = i;
            y /= 2;
         }
         if (judge[I] == 0){
            judge[I] = x;
            break;
         }
         x ^= judge[I];
      }
      if (S[n] != '0'){
         if (x != 0)
            z = 1;
      }
   }
   return z;
}
int main(){
   vector<int> A = { 1, 2 };
   string S = "10";
   cout << solve(A, S) << endl;
}

入力

{ 1, 2 }, "10"

出力

1

計算量

各要素に対して最大60回程度の簡約処理を行うため、時間計算量は O(N × 60)、空間計算量は O(60) ＝ O(1) となります。Nが大きい場合でも高速に動作する実用的な手法です。