SRM539 Div1 Easy - Over9000Rocks
問題
石を無限に持っていて、9001個以上の石を箱に詰めたい
n個の箱があり、i番目の箱にはx[i]個以上y[i]個以下の石を詰めることができる
詰める石の個数が何通りあり得るか求めよ
1 <= n <= 15
1 <= x[i], y[i] <= 10^6
解法
2^15通り全列挙して使う箱の組み合わせを全部試す
使うと決めた箱たちのΣx[i]をsl、Σy[i]をsrとすると、詰める石の総数として有効な範囲は[max(sl,9001),sr]となる
この左端と右端のペアをvectorに突っ込んでソートしてマージしていけば良い
実装
最後マージするところのrは「答えに加算した範囲の右端」って意味
class Over9000Rocks { public: int countPossibilities(vector<int> x, vector<int> y) { int n = x.size(); vector<pair<int,int> > p; rep(i,1<<n) { int l = 0, r = 0; rep(j,n) if (i>>j&1) l += x[j], r += y[j]; if (9000<r) p.push_back({max(l,9001), r}); } sort(all(p)); int res = 0, r = 0; each(i,p) if (r<i.second) { res += i.second - max(r+1, i.first) + 1; chmax(r, i.second); } return res; } };