TopCoder SRM 639 Div1 Easy AliceGame

引っかかってしまった。
http://community.topcoder.com/stat?c=problem_statement&pm=13490

問題

基本的な問題設定はDiv2 Mediumと同じ。
TopCoder SRM 639 Div2 Medium AliceGameEasy - kmjp's blog

ただし、i回目の対戦で得られるポイントが2*i-1である点が異なる。

解法

まず、M回目までのポイント合計に関しM*M == x+yとなるMの有無を判定する。

その後、Div2 Medium同様に大きい順にxからポイントを引いていく。
ただし注意点として、x==2となるようなポイントの引き方はできない。
対戦で得られるポイントをどう足しても、2点にはならないためである。

class AliceGame {
	public:
	long long findMinimumValue(long long x, long long y) {
		ll i,w=0;
		for(i=0;i*i<x+y;i++);
		if(i*i!=x+y) return -1;
		
		for(;i>=1;i--) {
			if(x>=i*2-1 && x!=i*2+1) x-=i*2-1, w++;
			else y-=i*2-1;
		}
		
		if(x==0 && y==0) return w;
		return -1;
	}
}

まとめ

本番2点になると成立しないことには気づいたが、引く時点で2にならないようにすることには意識が及ばなかった。