TopCoder SRM 710 Div1 Medium MagicNim

これは考察が重い。
https://community.topcoder.com/stat?c=problem_statement&pm=14529

問題

Nimの変形版を考える。
N+1個の石の山があり、うちN個がそれぞれA[i]個の石でできている。
残り1個の山は特殊な石1個だけで構成されている。

ここでこれらの石を使い、Nimを行う。
一般的なNimは、最後の石を取ったものの勝ちである。
ただし、このNimでは特殊な石を拾った側は、勝利条件を反転させるかどうか選択可能である。

与えられた石の状態に対し、先手後手どちらが必勝か答えよ。

解法

Editorialもあるが、下記のブログの方がわかりやすい。
SRM710 - sigma425のブログ

ほぼ同じ内容となるが、一応説明。
いきなり回答を書くが、先手必敗な条件は下記の通り。

1. 残された山のうち石の数が4以上のものがある場合、A[i]のxorを取った値が1
2. そうでない場合、A[i]のxorを取った値が2

これが正しいことを示すには、必敗な状態のターンで何をやっても必敗でない状態になり、逆に必敗でない状態のターンからは(次の相手のターンが)必敗な状態に持って行けることを示せばよい。

まず、前提として下記のケースは先手必勝である。

• すべての山の石の数が1以下の場合、以後の山の減り方は一意なので、特殊な石を取って勝利条件を決めることができるので、必勝である。
• 特殊な石を除いたすべての山の石の数のxorを取った値が0のとき、特殊な石を取りつつ勝利条件を変えなければ、以後普通のNimとなるうえ、相手が必敗の状態となる。

これを踏まえ、上記必敗な状態からの遷移を考える。
前提として、石を1つでも拾うと、xorを取った値は必ず変化する。

• 石の数が4以上の山があり、xorを取った値が1のとき：
  • xorの値が0になる取り方は、上記のとおり相手の必勝パターンになるのでそれはできない。よってxorを取った値は2以上にすることしかできない。また、4以上の山があるのにxorの値が1ということは4以上の山は偶数個ある。
  • よって、xorの値が2以上にしても、相手のターンでまだ石の数が4以上の山が1個以上ある状態で、xorの値を1に戻される。
• 石の数がすべて3以下があり、xorを取った値が2のとき：
  • xorの値が0になる取り方は、上記のとおり相手の必勝パターンになるのでそれはできない。
  • とするとxorの値を1か3にするしかない。
    • 3にした場合、相手の手番で再度3→2に戻す方法が必ずあるので、またxorの値を2に戻される。
    • 1にした場合、すべての山の石の数が1以下なら先手必勝条件より相手が勝つし、そうでないなら2以上の山があるので再びxorの値を2に戻される。

よって必敗な状態になると、どうやっても相手の手番でまた必敗な状態に戻される。

class MagicNim {
	public:
	string findWinner(vector <int> arr) {
		int nim=0;
		sort(ALL(arr));
		FORR(r,arr) nim ^= r;
		
		return (nim==(2-(arr.back()>=4)))?"Bob":"Alice";
	}
}

まとめ

これ想定解で解いた人数人いるけどすごいな。