yukicoder : No.1363 [Zelkova Last Tune] 誰がその最後のベルを鳴らすのか?

問題設定がややこしいね。
https://yukicoder.me/problems/no/1363

問題

以下の変形Nimを考える。
初期状態では、各山の石の数A[i]と山固有のパラメータP[i]がある。
また、両プレイヤーは山とは別にそれぞれX個・Y個の石を持つ。

まず以下を行う。
両プレイヤー交互に、手持ちの石のうちいくつか消費し、新たな山を作る。
また、その際その山に対してもパラメータを任意に設定する。
この手順はパスをしてもよく、両者パスすると終了する。

次に、もともと後手だった人から、2段階目を行う。
こちらはNimと似たルールだが、各山一度に取り除ける石の数はP[i]までである。

最適手を取ったとき、勝者はどちらか。

解法

後者は、石の数AとパラメータPの時、Grundy数はA%(P+1)となるので、2段階目が始まったとき、Xor(A[i]%(P[i]+1))が非0なら2段階目の先手(もともとの後手)が必勝である。

初期状態のGrundy数のxorをGとする。
Y≧X+Gなら元の先手が勝利。というのも自分の手番で常にGを0に持ち込めるためである。

int T;
int K;
ll A[1010],P[1010],X,Y;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K>>X>>Y;
		FOR(i,K) cin>>A[i];
		ll G=0;
		FOR(i,K) {
			cin>>P[i];
			G^=A[i]%(P[i]+1);
		}
		if(Y>=X+G) {
			cout<<"C"<<endl;
		}
		else {
			cout<<"Z"<<endl;
		}
		
	}
}

まとめ

この考察、本番中にサクッと出せる気がしないなぁ。