2026-11-05
first_wins.c
#include <stdio.h>
int main(void) {
int pile[] = {5, 1};
int x = 0;
for (int i = 0; i < 2; i++) {
x ^= pile[i];
}
puts(x != 0 ? "first" : "second");
}
いくつかの石の山を使い、2人が交互にどれか1つの山を選んで、そこから1〜3個の石を取ります。取れなくなった人が負けです。このプログラムは、山ごとの局面の値をXORし、0でなければ先手の勝ちとして first、0なら後手の勝ちとして second を表示するつもりで書かれています。山の局面の値は、取れる手が無ければ0、それ以外は1手で移れる局面の値のどれとも等しくない最小の非負整数と決めます。石が5個と1個の山で始めると、いまは first と表示されますが、本来は second です。
Answer
Wrong
for (int i = 0; i < 2; i++) {
x ^= pile[i];
}
このループがXORしているのは山の石の数で、局面の値ではありません。2つが一致するのは、1つの山から何個でも取れるゲームだけです。そのときは石が k 個の山から0〜k − 1 個のどれにでも移れるので、値は k になります。取れるのが1〜3個に限られると、値は石の数とずれます。0個は0で、1〜3個はそれより少ないどの個数へも移れるので、それぞれ1、2、3です。4個の山は1〜3の局面にしか移れず、0になります。値は4個ごとに0、1、2、3を繰り返し、石が n 個の山の値は n % 4 です。
入力の山は5個と1個なので、本来XORするのは 5 % 4 = 1 と 1 % 4 = 1 で、結果は0です。ところがループは石の数そのものを使い、5 ^ 1 = 4 を得て first を表示します。実際、先手が5個の山から1個取って4個と1個にすると、後手は1個の山を取り切り、先手は取り切れない4個の山だけを残されます。先手がほかの手を選んでも、後手には値のXORを0に戻す手が必ずあります。
Right
for (int i = 0; i < 2; i++) {
x ^= pile[i] % 4;
}
山ごとに石の数を局面の値 pile[i] % 4 に直してからXORします。いくつかの山を並べたゲーム全体の値は、山ごとの値のXORになる1ので、XORを取る式はそのままでよく、XORに入れる値だけが間違っていました。5個と1個では1と1のXORで0になり、second が表示されます。石の数のXORで勝敗を決める見慣れた方法は、取れる個数に上限が無いゲームでだけ使えます。
- この性質はスプレイグ・グランディの定理(Sprague-Grundy theorem)と呼ばれ、局面の値はGrundy数(グランディ数、Grundy number)と呼ばれます。取れる個数に上限が無いゲームはNim(ニム)と呼ばれ、山の値が石の数そのものになるので、石の数のXORで勝敗が決まります。