TopCoder SRM 615, Division 1, Level 1 : AmebaDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13088&rd=15848

問題概要

　アメーバは、自分と同じサイズのジェルに出会うとそれを吸収して二倍の大きさになる。今、数列 X が与えられる。X の i 項目の要素は、アメーバが i 番目に出会うジェルの大きさである。アメーバの初期の大きさは任意の正の整数をとることができる。全てのジェルに出会った後のアメーバの大きさとなり得ない整数の数を求めよ。

解法

　X の要素数を N と表記します。
　初期状態としてとれる値が多いので、適当に候補を絞る必要があります。X に出現しない値を初期状態とした場合はアメーバの大きさが変化しないので、そのような値は必ず作ることができます。従って、作れない可能性があるのは X に含まれる値だけです。また、X に含まれない値を初期値にしても X に含まれない（＝必ず作れる）値にしかならないので、初期値として考慮する必要も無いことが分かります。つまり、意味のある結果をもたらす初期値は X に含まれる値だけということになります。そのような値は 個しかありません。
　初期値を決めたときの最終的な値は のシミュレーションで計算できるので、最終状態の列挙は でできます。後は、適当なやり方（ e.g. std::set を用いる）で、X に出現するが最終的な大きさには現れない値の数を数えることで答えが得られます。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

class AmebaDiv1
{
public:
	int count( vector <int> X )
	{
		VI nums( X );
		sort( ALL( nums ) );
		nums.erase( unique( ALL( nums ) ), nums.end() );

		set<int> results;
		FOR( c, nums )
		{
			results.insert( accumulate( ALL( X ), c, []( const int cur, const int x ){ return cur == x ? cur * 2 : cur; } ) );
		}

		int res = 0;
		FOR( n, nums )
		{
			res += !EXIST( results, n );
		}
		return res;
	}
};