C++で解く「黒板XORゲーム」― 先手・後手の勝敗を決めるシンプルな判定条件

問題の概要

黒板には配列 nums の各要素が書き込まれています。ラム（Ram）とサム（Sam）の2人が交互に黒板からちょうど1つの数字を消していき、先手はラムです。

ルールは次の通りです。

• 数字を消した結果、黒板上の全要素のビット単位XORが0になった場合、その消したプレイヤーは負けとなります。
• 要素が1つだけの場合、そのXORは要素自身の値、要素が1つもない場合のXORは0として扱います。
• 自分のターンを始める時点で、すでに黒板上の全要素のXORが0になっている場合、そのプレイヤーは勝ちとなります。

具体例：nums = [1, 2, 1]

ラムが最初に 1 を消すと、残りは [2, 1] となり、全体のXORは 2 XOR 1 = 3 です。ここでサムはどちらの要素を消しても構いません。いずれの場合も、最後の1要素を消すのはラムとなり、その瞬間にXORが0になるため、ラムは負けてしまいます。

一方、ラムが最初に 2 を消すと、残りは [1, 1] となり、この時点で全体のXORは 0 になります。「消したことでXORが0になったプレイヤーは負ける」というルールに抵触するため、こちらもラムの負けです。

一見複雑そうなゲームですが、実はごくシンプルな条件だけで勝敗を判定できます。

解法の考え方

結論から言うと、「初期状態の全要素のXORが0である」または「配列の長さnが偶数である」場合に限り、先手（ラム）が勝ちます。それ以外の場合は後手の勝ちです。

判定の手順は以下の通りです。

• n := 配列 nums のサイズ
• x := 0
• nums の全要素 i に対して以下を実行：
  • x := x XOR i
• x == 0 または n mod 2 == 0 を返す

これが成り立つ理由はこうです。XORの総和が0なら、先手はターン開始時点で即座に勝利条件を満たします。総和が0でない場合でも、要素数が偶数であれば「消してもXORが0にならない要素」が必ず存在するため、先手は毎ターン安全な手を選び続けることができます。逆に要素数が奇数の場合は、同じ戦略が後手側に成立します。

C++による実装例

理解を深めるために、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool xorGame(vector<int>& nums) {
      int n = nums.size();
      int x = 0;
      for(int i : nums) x ^= i;
      return x == 0 || n % 2 == 0;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1};
   cout << (ob.xorGame(v));
}

入力

{1,2,1}

出力

0

出力が 0（false）になるのは、配列 [1, 2, 1] の全体XORが 2 で0ではなく、要素数も奇数の3であるためです。つまりこのケースでは先手のラムが負けることを意味しています。