TopCoder, Single Round Match 653, Division 2, Level 1 : CountryGroup

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13687&rd=16317

問題概要

　何人かの人が一列に並んでいる．人々は，出身が同じ人同士は連続した位置に座っていることが分かっている．それぞれの人に対し，「同じ出身の人は何人いるか」という質問をした．質問の答えから，出身地が全部で何箇所あるか，求めよ．回答に矛盾がある場合は -1 で示せj．
　質問の答えは配列 により与えられ， が左から 番目の人の回答である．

解法

　 を と書きます．
　題意より，質問への回答が同じ人同士は出身地が同じ可能性がありますが，確定ではありません．例えば， のとき，出身地の並びは のような並びでなければなりません．言えるのは，左から確定させていくと考えると，ある位置で を発見したとき，（その人を含め）連続する 人は同じ出身でなければならないということです．この条件に反するとき，回答が矛盾しているので問題の答えは -1 となります．条件に違反しないならば，その 人の出身が同じであるとして仮の答えに 1 を足します．残りの人々について同じように処理していくと（途中で矛盾が出なければ）全ての人の出身を確定できるので，問題を解くことができます．
　この処理をするとき，各人について着目するのは，未確定の人の内最も左にいる人の回答を参照するときと，そこから連続する範囲で回答が矛盾しないことを確かめるときの高々 2 回なので， 時間で処理することができます．

コード

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )

#define SZ( v ) ( (int)( v ).size() )

class CountryGroup
{
public:
	int solve( vector <int> a )
	{
		const int N = SZ( a );
		int res = 0;
		REP( i, N )
		{
			if ( N < i + a[i] || count( a.begin() + i, a.begin() + i + a[i], a[i] ) != a[i] )
			{
				return -1;
			}
			++res;
			i += a[i] - 1;
		}
		return res;
	}
};