kmjp's blog

競技プログラミング参加記です

TopCoder SRM 639 Div2 Medium AliceGameEasy

SRM639に参加。
前回に引き続きEasyのひっかけにあっさり引っかかってしまった。
Mediumをギリギリ解いてレート維持。とはいえ反省するところも多い。
http://community.topcoder.com/stat?c=problem_statement&pm=13524

問題

2人でゲームをしている。
i回目の対戦で勝利すると、勝利側にiポイントが加算される。

最終的に先手がxポイント、後手がyポイントだとする。
そのようなゲーム展開はあり得るか。
また、あり得るなら先手の最小勝利回数を答えよ。

解法

試合回数をMとすると、合計得点に関しM*(M+1)/2 == x+yというMがあるかないか総当たりする。
そのようなMがなければ展開はない。

M*(M+1)/2 == x+yとなるMが見つかったら、最小勝利回数を求める。
当然ポイントの多い試合に勝った方が勝利回数を抑えられるので、xからMポイント、(M-1)ポイント、(M-2)ポイント…と順に引ける限り引いて行き、その回数を求めればよい。

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

まとめ

こちらは楽なんだけどね…。