TopCoder SRM 606, Division 1, Level 1 ( Division 2, Level 2 ) : EllysNumberGuessing

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12975&rd=15839

問題概要

　次のような数当てゲームをする。

1. 出題側が正答を一つ決める
2. 回答側が数を言って、出題側は正答との差の絶対値を答えるという手順を複数回行う

質問の内容と答えのペアが与えられる。その情報から答えを一意に求めることができるならば、その答えを返せ。一意に定まらないとき、-1 で示せ。出題側が嘘を付いている（答えが存在しない）とき、-2 を返せ。

解法

　質問一回毎に解候補が二つ出てきます。出題側が用意した答えは、全ての質問から出てくる必要があるので、質問の回数を N とすると N 回出てきた数が最終的な解候補です。最終的な解候補が一種類であればその数が答えです。二種類以上あるとき、一意に定まらないので -1 を返します。そうでないとき（＝ 0 種類しかないとき）、答えが存在しないので -2 を返します。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define fst first
#define snd second

const int ds[] = { -1, 1 };

class EllysNumberGuessing
{
public:
	int getNumber( vector <int> guesses, vector <int> answers )
	{
		const int N = guesses.size();

		map<int,int> counts;
		REP( i, 0, N )
		{
			counts[ guesses[i] - answers[i] ]++;
			counts[ guesses[i] + answers[i] ]++;
		}

		set<int> res;
		FOR( p, counts )
		{
			if ( 1 <= p.fst && p.fst <= 1000000000 && p.snd == N )
			{
				res.insert( p.fst );
			}
		}

		if ( res.size() == 1 )
		{
			return *res.begin();
		}
		if ( 2 <= res.size() )
		{
			return -1;
		}
		return -2;
	}
};