AtCoder ARC #137 : C - Distinct Numbers

予定が合わず不参加。
https://atcoder.jp/contests/arc137/tasks/arc137_c

問題

整数列Aを用いた2人対戦のターン制ゲームを行う。
各人の手番では、Aのいずれかの要素を選び、より小さい正整数に置き換える。
ただし、複数要素が同じ値になることがあってはならない。

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

解法

Aを事前にソートしておく。

Aが大きいほど移動先の選択肢が大きいので、逆に自分の手番ではAの最大値を動かすと良い。
Aの最大値と2番目に2以上の差があるとき、後者のいずれのパターンにも持っていけるので先手必勝である。

そうでない場合、両者「Aの最大値とAの2番目の間に2以上の差ができない」ように動かすので、これは結局1～Aの最大値までの間にある隙間(Aに含まれない整数)の数が1個減ることになる。
よって、初期状態の隙間の偶奇で勝者が決まる。

int N;
int A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	if(A[N-2]+1!=A[N-1]) {
		cout<<"Alice"<<endl;
	}
	else if((N-1)%2!=(A[N-1]%2)) {
		cout<<"Alice"<<endl;
	}
	else {
		cout<<"Bob"<<endl;
	}
}

まとめ

これはすんなりわかった。