TopCoderOpen 2019 Round2A : Hard YetAnotherTokenGame

シンプルだけど割とややこしい。
https://community.topcoder.com/stat?c=problem_statement&pm=15473

問題

2人でNimを行う。
ただし、両者の手番で取れる手順はNimと異なり、以下のいずれかを行える。

• 通常のNim通り、山を1つ選択してその山の石の個数以下の任意の正整数個の石を取り除く。
• 2個以上石がある山を1つ選択し、複数の山に分割する。山の数は2個以上いくらでもよい。

解法

NimなのでGrundy数を求める。
X個の山のGrundy数をG(X)とする。
その際、同時にX個の石の山を分割した際に到達可能なGrundy数の一覧をS(X)とする。
これらをXの小さい順に同時に求めていこう。

X個の石の山を分割した際、1つ目の山の石がp個であり、残り(X-q)個をさらに分解するとする。
S(X)にはs∈S(X-q)に対し(G(p) xor s)が追加される。

S(X)がわかれば、X個の山から遷移可能なGrundy数の一覧が列挙できるので、そのMex値を求めればよい。
G(X)がXより大きい場合もあるので、配列のサイズに注意。

int G[305];
int ok[305][505];

class YetAnotherTokenGame {
	public:
	string getWinner(vector <int> piles) {
		ZERO(ok);
		ZERO(G);
		ok[0][0]=1;
		int i,j,x;
		for(i=1;i<=300;i++) {
			for(j=1;j<i;j++) {
				for(x=0;x<=500;x++) if(ok[i-j][x]) ok[i][G[j]^x]=1;
			}
			int did[504]={};
			FOR(j,i) did[G[j]]=1;
			FOR(j,503) if(ok[i][j]) did[j]=1;
			
			while(did[G[i]]) G[i]++;
			ok[i][G[i]]=1;
		}
		
		int nim=0;
		FORR(p,piles) nim^=G[p];
		return nim?"William":"Xenia";
	}
}

まとめ

これ本番で出てたら結構苦戦しそう。