AtCoder ARC #148 : D - mod M Game

もうちょい頑張りたかった回。
https://atcoder.jp/contests/arc148/tasks/arc148_d

問題

2N個の整数列と、正整数Mが与えられる。
2人で交互に整数を選び整数列から抜き出すことを考える。
最終的に両者それぞれの抜き出した整数の和をMで割った値が、一致すれば後手、不一致なら先手の勝ちとする。

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

解法

• Mが奇数の場合、登場頻度が奇数の値が1個でもあれば先手必勝、そうでなければ後手必勝である。
• Mが偶数の場合、整数aとa+M/2の登場回数の和が奇数の場合、先手必勝である。
  • 整数aとa+M/2の登場回数の和がすべて偶数でも、a+M/2の形の登場回数が奇数の場合、先手と後手をM/2だけ差が付くようになるので先手必勝である。

int N;
ll M;
ll A[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	map<int,int> S;
	ll sum=0;
	FOR(i,2*N) {
		cin>>A[i];
		S[A[i]]++;
		sum+=A[i];
	}
	
	if(M%2) {
		FORR2(a,b,S) {
			if(b%2) {
				cout<<"Alice"<<endl;
				return;
			}
		}
		cout<<"Bob"<<endl;
	}
	else {
		int sum=0;
		FORR2(a,b,S) if(a<M/2) {
			x=b;
			y=0;
			if(S.count(a+M/2)) y=S[a+M/2];
			if((x+y)%2) {
				cout<<"Alice"<<endl;
				return;
			}
			sum+=y;
		}
		if(sum%2==0) {
			cout<<"Bob"<<endl;
		}
		else {
			cout<<"Alice"<<endl;
		}
		
		
		
	}
	
}

まとめ

なんか本番割とすんなり解いてたな。