TopCoder SRM 615 Div1 Easy AmebaDiv1

SRM615に参加。
またもEasy+Chalでレート微増。
http://community.topcoder.com/stat?c=problem_statement&pm=13088

問題

N要素の整数配列X[i]が与えられる。

初期状態の数値をPとしたとき、最終状態の数値は以下の手順で得られる。

• PをX[0]～X[N-1]まで順に比較していく。P==X[i]となるようなX[i]が見つかったら、Pを2倍にし、またX[i+1]以降と比較していく。
• X[N-1]まで比較した後の数値Pが最終状態。

最終状態として存在しえない正の整数の数を答えよ。

解法

元々X[i]に含まれない数値をPとして選んだ場合、最終状態まで数値はPのままなので、それらは常に最終状態として存在しうる。
よってP=X[0]～X[i]をそれぞれ初期状態として最終状態を求め、X[0]～X[i]のうち到達できない最終状態の数を求めればよい。
O(N^2)で終わるので時間は余裕。

class AmebaDiv1 {
	public:
	int count(vector <int> X) {
		int N=X.size(),i;
		set<int> S,S2;
		ITR(it,X) S.insert(*it);
		int j=0;
		ITR(it,S) {
			int x=*it;
			FOR(i,N) if(x==X[i]) x<<=1;
			if(S.find(x)!=S.end()) S2.insert(x);
		}
		
		return S.size()-S2.size();
	}
};

まとめ

Mediumが解けないのは残念だけど、ここ数回Easyが安定しているのが良い。