AtCoder ARC #105 : D - Let's Play Nim

若干エイヤで通してしまった。
https://atcoder.jp/contests/arc105/tasks/arc105_d

問題

以下のような変則Nimを考える。
N個の袋にそれぞれいくつか正整数個のコインが入っており、それとは別にN個の空の皿がある。
2人交代でターンが回ってくる際、最初のN手までは両者コインの入った袋を1つ選び、どこかの皿に中身をすべて出す。
この時、すでにコインが乗った皿に追加する形でも構わない。

全袋の中身がなくなったところで、コインの乗った皿を山に見立てNimを行う。
この時の先手は、最後に袋の中身を出した方の逆である。

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

解法

最後に袋を開ける側は、各山のコインのxorを0となるようにしてくる。
反対のプレイヤーがそれを防げるかを考えよう。

• Nが偶数の時
  • 各コイン数の袋がすべて偶数の時、後手は先手の真似をすることでxorを0にでき、後手必勝。
  • そうでない場合、先手はとにかくコインの多い袋を開けて一番コインの多い皿に追加していくと、1つの皿が過半数のコインを持つ状態にでき、最後に後手がどうやってもxorを0にできず先手必勝。
• Nが奇数の時
  • 後手が同様に一番コインの多い皿をさらに多くするようにすると、袋を開ける最後の先手の手番でxorを0にできないようにでき、後手必勝。

int T,N;
ll A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		map<int,int> M;
		FOR(i,N) {
			cin>>A[i];
			M[A[i]]++;
		}
		if(N%2==0) {
			int odd=0;
			FORR(m,M) if(m.second%2) odd++;
			if(odd==0) {
				cout<<"Second"<<endl;
			}
			else {
				cout<<"First"<<endl;
			}
		}
		else {
			cout<<"Second"<<endl;
		}
	}
}

まとめ

自信をもって通すのちょっと難しい。