SRM 539 250pt : Over9000Rocks
問題概要
N(≦16)個の箱があり、各箱の中には石が十分たくさん入っている。この箱の中からいくつか選び、lower[i]以上upper[i](1
解法
愚直に塗りつぶしたりsegtree使ったりしても解けるらしいけど、時間空間ともに危険域なので別の方針で頑張る。
部分集合を全列挙して下界の和と上界の和を選んで(9000, inf)との共通部分をとる。
acceptされたコード
#include <vector> #include <algorithm> using namespace std; struct Over9000Rocks { int countPossibilities(vector <int> lowerBound, vector <int> upperBound) { const int N = lowerBound.size(); vector<pair<int,int> > rs; for(int bit=0; bit<(1<<N); bit++){ int lower = 0, upper = 0; for(int i=0; i<N; i++)if( (bit>>i)&1 ){ lower += lowerBound[i]; upper += upperBound[i]; } if(upper > 9000){ rs.push_back(make_pair(max(9001, lower), upper)); } } sort(rs.begin(), rs.end()); int ans = 0; int pl = 0, pu = 0; for(int i=0; i<(int)rs.size(); ++i){ pl = max(pl, rs[i].first); pu = max(pu, rs[i].second); if(pl <= pu){ ans += (pu - pl + 1); } pl = pu + 1; } return ans; } };