SRM737 Div1 Easy - AliceAndBobEasy

問題

nimのある状態において、その1手で勝利を確定させられるような石の取り方をwinning moveと呼ぶ
(ただし例えば(3,2,3)という状態から(1,2,3)と石を取るのと(3,2,1)とするのは別のmoveとする)
以下の条件を全て満たすnimの状態を1個作る
・山の数はn個 (1 <= n <= 37)
・任意の2つの異なる山に置かれている石の個数は異なる
・各山の石の個数は1以上7*10^8(くらい)以下
・↑を満たす状態の中でwinning moveの個数が一番多い

解法

nimにおいて勝利が確定ってのは「各山の石の個数のxor和が0の状態で相手にターンを渡す」ということ
つまり問題を言い換えると、xor和が0でなく、「i番目の山から、(i番目の山の石の個数)-(i番目以外の山のxor和) 個だけ石を取れる」ような山iが最も多いような状態を作りたい

(nが奇数のとき)
例えば各山の石の個数を1+64, 2+64, 3+64, ..., n+64にすれば、n個全ての山についてwinning moveが出来る
理由は、
①i番目の山の石の個数
②i番目以外の山の石の個数のxor和
とすると、①は下から6番目のビット(1<<6 = 64)が立っているのに対して②は立っていないから任意のiで①＞②となる
∴ 各要素についてwinning moveができる

(nが偶数のとき)
1つの山だけ石を1つにし、他の山は↑と同様の個数にすればn-1個の山についてwinning moveができる
n-1個の山について出来るのは↑と同じ理由
n個全ての山についてwinning moveができるような状態は存在しない
↓証明↓
各山の石の個数のxor和のうち立っているビットの最大値をXとすると、n=偶数よりXビット目が立っていない山が必ず1個は存在する
その山の石の個数をA、その山以外の全ての山の石の個数のxor和をBとする
Xより大きいビットはAとBは全て一致する
一方Xビット目は、Aでは立っていないのに対しBでは立っている
ゆえにA＜Bとなり、この山ではwinning moveができない
以上よりnが偶数のとき最低1個はwinning moveができない山が存在する

class AliceAndBobEasy {
public:
	vector<int> make(int n) {
		vector<int> res;
		if (n%2==0) res.push_back(1), n--;
		rep(i,n) res.push_back((1<<6)+i+1);
		return res;
	}
};