公式

C - Zero XOR 解説 by E869120

解説の目次

この解説は以下の 4 つのセクションから構成されます。

  1. 想定解法
  2. 想定解法の証明
  3. 解法を思いつくためのヒント
  4. サンプルコード

すぐに解法を知りたい人は、「1. 想定解法」をご覧ください。


1. 想定解法

答えは、以下のような場合分けによって求めることが可能です。（証明は「2. 想定解法の証明」を参照）

\(N\) が奇数の場合

先手必勝。

\(N\) が偶数の場合

1 手で机に残ったクッキーの XOR を 0 にできれば先手必勝。そうでなければ後手必勝（☆）。

すなわち、\(v = A_1 \ \text{XOR} \ A_2 \ \text{XOR} \ \cdots \ \text{XOR} \ A_N\) とするとき、\(A_1, A_2, \cdots, A_N\) のいずれかが \(v\) と一致していれば先手必勝。そうでなければ後手必勝（★）。この言い換えができる理由は 1.2 節参照。

したがって、以下のようなプログラムを書くと、正解が得られます。なお、\(N\) が偶数のときに ☆ を利用して愚直に判定すると計算量が \(O(N^2)\) となり TLE してしまうため（ソースコード）、★ を利用して判定していることに注意してください。

#include <iostream>
using namespace std;

int N, A[400009];
int v = 0;

int main() {
	// Step #1. 入力
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	
	// Step #2. A[1] xor A[2] xor ... xor A[N] を計算する
	for (int i = 1; i <= N; i++) v ^= A[i];

	// Step #3. 場合分け・出力
	if (N % 2 == 1) {
		cout << "Win" << endl;
	}
	else {
		bool winning = false;
		for (int i = 1; i <= N; i++) {
			if (A[i] == v) winning = true;
		}
		if (winning == true) cout << "Win" << endl;
		else cout << "Lose" << endl;
	}
	return 0;
}


1.2. ☆ と★ が同値である理由

☆ と ★ が同値である理由は、\(i\) 番目のクッキー以外の XOR を \(a\) として、\(i\) 番目のクッキーに書かれた整数を \(x\) とするとき、\(a \ \text{XOR} \ x \ \text{XOR} \ x = a\) であることから説明できます。イメージ図は以下の通りです。

※ XOR の性質より、一般の非負整数 \(a, x\) に対しても \(a \ \text{XOR} \ x \ \text{XOR} \ x = a\) が成り立ちます。


2. 想定解法の証明

想定解法が必ず正しい答えを出力することは、次のようにして証明することができます。


ステップ 1：2 手後にゲームが終わるか？

まず、以下の理由により、\(N\) が奇数のとき 2 手後にゲームが終わることは絶対にないことが証明できます。

ただし、2 手後にゲームが終わることは、「先手が手を打った後、後手が手を打ち XOR を 0 にし、後手が勝利する」ことを指します。

2 手後にゲームが終わるためには、少なくとも以下の条件を満たす必要があります。

  • どのような \(i\) \((1 \leq i \leq N)\) についても、先手が \(i\) 番目のクッキーを取った後、後手が XOR を 0 にする方法が存在する。（◆）

そこで ◆ を満たすと仮定し、先手が \(i\) 番目のクッキーを取った後、後手が \(P_i\) \((i \neq P_i)\) 番目のクッキーを取ったときに XOR が 0 になるとします。このとき、XOR の性質より、先手が \(P_i\) 番目のクッキーを取った後、\(i\) 番目のクッキーを取っても XOR が 0 になります。

これがすべての \(i\) \((1 \leq i \leq N)\) について成り立つので、\((i, P_i)\) のペアが \(N/2\) 個できるはずです。しかし、\(N\) は奇数なので、少なくとも 1 つ余りが出てしまいます（下図参照）。よって ◆ は満たされず、2 手後にゲームが終わることはありません。


ステップ 2：\(N\) が奇数のとき

まず、\(N=7\) の場合を考えてみましょう。ステップ 1 の性質により、以下のようにして先手必勝であることが証明できます。

  • クッキーが 7 個のとき、次の 1 手で先手が勝てるか、クッキーが 5 個になって先手のターンが回ってくるかのいずれかである。
  • クッキーが 5 個のとき、次の 1 手で先手が勝てるか、クッキーが 3 個になって先手のターンが回ってくるかのいずれかである。
  • クッキーが 3 個のとき、次の 1 手で先手が勝てるか、クッキーが 1 個になって先手のターンが回ってくるかのいずれかである。
  • クッキーが 1 個のとき、明らかに次の 1 手で先手が勝てる。よって先手必勝。

一般の奇数 \(N\) の場合も同じように証明することができます。ステップ 1 の性質を繰り返し適用すると、最終的にクッキーが 1 個になり、先手必勝だと分かります。


ステップ 3：\(N\) が偶数のとき

\(N\) が偶数のとき、先手のあなたが 1 手で決着を付けることができなければ、後手の E869120 君がステップ 2 と同じ状態になります。

よって、1 手で決着が付かない場合は後手必勝であることが分かります。


3. 解法を思いつくためのヒント

この問題は、解法の導出から証明までを行うのはかなり難しいです。しかし、AtCoder では証明などを行わなくても AC を出せれば得点が得られるため、いくつかのテストケースで実験して、規則性を見出す（実験エスパー）という方法が利用できる場合があります。

\(N=4\) 以上の大きいケースで実験しようとすると、手計算では時間がかかってしまいます。このようなときは、愚直解（たとえば全探索）を書いたり、ランダム生成されたテストケースで試したりするなどの方法を使うと良いです。詳しくは こちらの記事 をご覧ください。

なお、以下は全探索で本問題を解く C++ のプログラムとなっています。

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

// solve(vec) は、クッキーに書かれた整数が vec[0], vec[1], ..., vec[vec.size()-1] のときに
// 先手必勝であれば true、そうでなければ false を返す関数
bool solve(vector<int> vec) {
	// XOR が 0 であればゲーム終了（後手勝ちの状態）
	int All_XOR = 0;
	for (int i = 0; i < vec.size(); i++) {
		All_XOR ^= vec[i];
	}
	if (All_XOR == 0) {
		return false;
	}

	// そうでない場合
	for (int i = 0; i < vec.size(); i++) {
		// クッキー i を取った場合
		vector<int> nex;
		for (int j = 0; j < vec.size(); j++) {
			if (j != i) nex.push_back(vec[j]);
		}
		bool ret = solve(nex);
		if (ret == false) return true; // 先手必勝
	}
	return false; // 後手必勝
}

int main() {
	// 入力
	int N; cin >> N;
	vector<int> A(N, 0);
	for (int i = 0; i < N; i++) cin >> A[i];

	// 出力
	bool Answer = solve(A);
	if (Answer == true) cout << "Win" << endl;
	else cout << "Lose" << endl;
	return 0;
}


4. サンプルコード

投稿日時:
最終更新: