AtCoder ARC #143 : C - Piles of Pebbles

まぁまぁの出来だった回。
https://atcoder.jp/contests/arc143/tasks/arc143_c

問題

N個の石の山があり、それぞれA[i]個の石からなる。
ここで2人で行うターン制ゲームを考える。
各手番では、1つ以上いくつか山を選ぶ。
先手は、選んだ山から石をX個ずつ、後手はY個ずつ取り除くとする。
そのような山を選べなかった側が負けとなる。

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

解法

まず全部A[i]を(X+Y)で剰余を取った値に差し替えておこう。

先手が勝つ条件は以下である。

• A[i]がX以上のものが1個以上ある。(そうしないと、後手が先手の真似をすると先手はいずれ山を選べなくなる。)
• X≦YかつA[i]がX以上のものが1個以上あれば先手の勝ちである。そのようなものを1個以上選べば、後手に上を満たさない状況を押し付けられる。
• X>Yの場合、初手でA[i]がX以上のものを選ぶ必要がある。以後、前後反転すれば上の状況に持ち込める。

int N,X,Y;
int A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,N) {
		cin>>A[i];
	}
	
	int can=0;
	int lose=0;
	FOR(i,N) {
		if(A[i]%(X+Y)>=X) can++;
		if(A[i]<X&&A[i]>=Y) lose++;
		if(A[i]>=X&&(A[i]%(X+Y)<X&&A[i]%(X+Y)>=Y&&(A[i]-X)%(X+Y)>=Y)) lose++;
	}
	
	if(can&&lose==0) {
		cout<<"First"<<endl;
	}
	else {
		cout<<"Second"<<endl;
	}
	
	
	
}

まとめ

Nimでも偶奇判定でもない結果になるのは珍しい？