AtCoder AGC #002 : E - Candy Piles

正解に近いところまでは行けたのだけども。
http://agc002.contest.atcoder.jp/tasks/agc002_e

問題

N個のキャンディの山がある。各山はA[i]個のキャンディからなる。

これらの山を用いて、２人で交互にキャンディを取るゲームを行う。
各自の手番で、以下の何れかの取り方ができる。

• 一番残ったキャンディの多い山のキャンディを食べきる
• キャンディの残っているすべての山から１つずつキャンディを食べる

最後のキャンディを食べた方が負けとなる。
両者が最適手を取った場合、勝者はどちらか。

解法

まずA[i]を降順にソートしておこう。
この問題の勝ち負けじょ条件を言い換えると、以下のようになる。

• 縦Nマス分、各行に横A[i]マスを並べたヤング図形を考える。左上の点を(0,0)とし、右にマスx個分、下にy個分移動したヤング図形上の頂点を(x,y)と表現することにする。
• この図形上で、(0,0)から初めて両者のターンで交互に辺を右か下に移動するとき、ヤング図形の周辺部に先に到達すると負けになる。
  • (逆に、周辺部に到達した状態で自分のターンが来たら勝ち)

右か下どちらかに移動することで、相手が負け確定になるポイントに移動できるなら、自分は勝ち、というルールに則りヤング図形の各頂点の勝ち負けを判定していけば、初期状態(0,0)で先手が勝つか負けるかわかる。
ただしこの手順はO(N*max(A))かかりTLEする。

ここで勝ち負けがヤング図形上でどう決まるか法則性を見出すと、周辺部以外は(x,y)の勝ち負けは(x+1,y+1)と一致することがわかる。
よって、(a,a)が図形の内部で、(a+1,a+1)が図形の周辺部に来るような整数aを考えると、(a,a)の勝ち負けを求めれば(0,0)の勝ち負けが求められる。
(a+1,a+1)は既に周辺部なので、(a,a)で先手の手番が回ってきたとき、そこで右と下どちらに移動するかを決めると、後は選択肢がなくなる(ずっと右に行き続けるか下に行き続けるしかない)。
これらのケースの勝ち負けは容易に求められるので、右か下どちらかに移動することで先手が勝利できるなら、(a,a)及び(0,0)においても先手が勝利できる。

int N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	reverse(A,A+N);
	
	FOR(i,N) if((A[i]<=i+1 || A[i+1]<=i+1) {
		y=i;
		while(A[y]>i) y++;
		
		if((A[i]-i)%2 && (y-i)%2) return _P("Second\n");
		return _P("First\n");
	}
	
}

まとめ

本番、ヤング図形そのものではないものの似たアイデアには到達したが、勝ち負けが斜めに並ぶことに確証が持てず正答にたどり着けなかった。