TopCoder, Single Round Match 653, Division 1, Level 1 : CountryGroupHard

問題文

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

問題概要

　何人かの人が一列に並んでいる．人々は，出身が同じ人同士は連続した位置に座っていることが分かっている．それぞれの人に対し，「同じ出身の人は何人いるか」という質問をしたが，何人かの人からは回答を得られていない．
　回答は配列 によって与えられる． が正整数のとき，それは 番目の人から得られた回答を表す． のとき， 番目の人からは回答を得られていない．
　回答が矛盾しない出身地の組合せがただ一通りに定まるか？
　

解法

　 を と書きます．
　左端から順に出身地を割り振っていくと考えます．正確には，未確定の人の内最も左端の人に着目して，「何人の人を同郷にするか」を全通り試すという探索を考えます．やっていることは数え上げなので，決めた人数が同じであれば同じ状態としてしまう動的計画法を考えることができます．すなわち，

• dp[ 考慮した人数 ] := 何通りあるか

という具合に状態をとった DP をします．
dp[ i ] からの更新は， 人目から（連続する）何人を同郷にするかを全て試すことになるので，同郷にする人数を として，

• dp[ i + j ] に dp[ i ] の値を足し込む

という更新になります．ただし，回答が矛盾しないようにするための条件として， 上の区間 から得られた回答が，次の 2 条件の内いずれかを満たしている必要があります．

• 回答が全く得られていない
• 回答が 1 通りであり，かつそれが同郷にしようとしている人数 に等しい

いずれかの条件を満たす場合に限り，その区間を同郷にしても矛盾しないので，上述の更新を適用します．この条件を判定するために，std::set に回答を insert してユニーク or 空 or それ以外の判定を行いました．
　更新が終わったあと，dp[ N ] の値が 1 か否かで問題の答えが分かります．
　また，今回の場合，1 通りかそれ以外かだけが分かればよいので，2 通り以上存在する場合は全て 2 にまとめてしまいます（オーバーフローで変なことになると怖い）．
　この解法の計算量ですが，状態数 に対して選択肢の数も であり，選択肢毎に std::set を定数回操作するので，全体では 時間となります．

コード

using VI = vector< int >;

#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 CountryGroupHard
{
public:
	string solve( vector <int> a )
	{
		const int N = SZ( a );

		VI dp( N + 1, 0 );
		dp[0] = 1;

		REP( i, N )
		{
			set< int > s;
			for ( int j = 0; i + j < N; ++j )
			{
				if ( a[ i + j ] )
				{
					s.insert( a[ i + j ] );
				}

				if ( s.empty() || SZ( s ) == 1 && *s.begin() == j + 1 )
				{
					dp[ i + j + 1 ] += dp[i];
					dp[ i + j + 1 ] = min( dp[ i + j + 1 ], 2 );
				}
			}
		}

		return dp[N] == 1 ? "Sufficient" : "Insufficient";
	}
};