kmjp's blog

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

TopCoder SRM 606 Div1 Easy EllysNumberGuessing

SRM606は不参加なので練習のみ。
Easyはさっくり解いたけど、Mediumが1発正解できなかったので出てもレートは変動なさそうだったな。
http://community.topcoder.com/stat?c=problem_statement&pm=12975

問題

相手は1~10^9のいずれかの数字を頭に浮かべており、その数を当てるゲームを行う。
こちらが数字を伝えると、頭に浮かべている数字との差の絶対値を教えてくれる。

伝えた数字guesses[i]と教えてくれた数字answer[i]のペアがいくつか与えられるので、頭に浮かべた数字を当てよ。

解法

答えはguesses[0]+answer[0]かguesses[0]-answer[0]のどちらかなので、それら両方の数字について、他のguesses[i],answer[i]のペアと矛盾しないものを残せばよい。

答えが1未満や10^9を超えることはない点に注意。

class EllysNumberGuessing {
	public:
	int getNumber(vector <int> guesses, vector <int> answers) {
		int N=guesses.size();
		ll l,h;
		int i;
		l=h=guesses[0];
		l-=answers[0];
		h+=answers[0];
		if(h>1000000000) h=-1;
		if(l<1) l=-1;
		
		FOR(i,N) {
			if(h!=guesses[i]+(ll)answers[i] && h!=guesses[i]-(ll)answers[i]) h=-1;
			if(l!=guesses[i]+(ll)answers[i] && l!=guesses[i]-(ll)answers[i]) l=-1;
		}
		
		if(l!=-1 && h!=-1) return -1;
		if(l==-1 && h==-1) return -2;
		if(l==-1) return (int)h;
		return (int)l;
	}
}

まとめ

今回のEasyは簡単だったようで平均点も高め。