TopCoder SRM 621 Div2 Medium NumbersChallenge

割とオーソドックスな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13086

問題

N要素からなる正の整数の集合Sが与えられる。
個々の要素の上限Lは10^5である。
正の整数のうち、Sの部分集合の和で表現できない最小の値を答えよ。

解法

ナップサック問題の要領でDPしても良いし、N≤20と小さいことを利用してbitmaskを用いて全部の部分集合の和を列挙してもよい。
普通にDPするとO(NL)、部分集合の列挙はO(N*2^N)なので、今回のケースはどちらでも解ける。

以下のコードは後者の解法。
部分集合の和をsetで管理しているが、上限は高々2*10^6なので部分集合の和として登場したかどうかを配列で管理しても良い。

class NumbersChallenge {
	public:
	int MinNumber(vector <int> S) {
		set<int> SS;
		int N=S.size(),i,mask;
		FOR(mask,1<<N) {
			int tot=0;
			FOR(i,N) if(mask&(1<<i)) tot+=S[i];
			SS.insert(tot);
		}
		for(i=1;;i++) if(SS.find(i)==SS.end()) return i;
		
	}
}

まとめ

Lが大きくNが小さいことを除けばオーソドックスなDP問題。