TopCoder SRM 539 Div2 Meidum Over9000Rocks

問題

n個の箱があり、それぞれに次の条件を満たすように石をいくつか入れる。

• 石は無限にある
• i番目の箱には、石をまったく入れないか、lowerBound[i]以上upperBound[i]以下の石を入れる。
• 全ての箱の石の合計が9000個より多い

このとき、全ての石の合計としてありえる値は何通りあるか、求めよ。

制約条件

n≦15
lowerBound[i], upperBound[i]≦10^6

方針

使う箱の選び方は2^n通りなので、全通り試す。
使う箱を決めると、値として可能な区間が求まるので、
区間はmapに開始位置を+1、終了位置を-1として覚えておけば、
mapをなめることで区間の併合の長さが求められる。

ソースコード

class Over9000Rocks {
	public:
	int countPossibilities(vector <int> lowerBound, vector <int> upperBound) 
	{
		int n = lowerBound.size();
		map<int, int> m;
		rep(i, 1<<n){
			int ls = 0, us = 0;
			rep(j,n) if(i & 1<<j){
				ls += lowerBound[j];
				us += upperBound[j];
			}
			m[ls]++; m[us+1]--;
		}
		int cur = 0, ans = 0;
		fr(i, m){
			map<int, int>::iterator it = i;
			if(++it == m.end()) break;
			
			cur += i->second;
			if(cur > 0){
				if(it->first <= 9001) continue;
				if(i->first >= 9001) ans += it->first - i->first;
				else ans += it->first - 9001;
			}
		}
		return ans;
	}
};