SRM 539 Div2 Medium Over9000Rocks

問題

9000個より多くの石を披露したい(なぜかは知らない,元ネタがある?).書く箱にはlowerBoundからupperBoundまでの石が入っている.箱にある石を組み合わせて披露できる石の数の種類を答えよ.

解答

箱の数が15個までなので,箱の組み合わせパターンは2^15 = 32768と少ないので全探索するのが良さそうだ.後は重複する数が存在するのでそれをうまく取りまとめれば良い.箱の組み合わせパターンで表現できる数はlowerBoundの総和からupperBoundの総和までの範囲として表現できるので.範囲のリストを互いに素になるようにマージすることが出来れば,単純な足し算で解を求めることが出来る.
このマージ作業に手こずって,最初に提出したコードはシステムテストでTLEしてしまった.
後々考え,範囲リストを,lowerBoundでソートすれば箱の総組み合わせパターンの範囲リストを線形に読み込むだけで良いことに気づく.こちらは高速に動作し,システムテストももちろん通る.

TLEするコード

class Over9000Rocks
{
public:
  int countPossibilities(vector <int> lowerBound, vector <int> upperBound)
    {
      set<int> vs;
      int i, j;
      int n = lowerBound.size();
      vector<int> lbands;
      vector<int> rbands;
      for(i = 1; i < (1 << n); i++){
        int low = 0;
        int upp = 0;
        for(j = 0; j < n; j++) if ((i >> j) & 1){
            low += lowerBound[j];
            upp += upperBound[j];
          }
        vector<int> lbands2;
        vector<int> rbands2;
        bool pushed = false;
        for(j = 0; j < lbands.size(); j++){
          if ((low <= rbands[j] && lbands[j] <= upp) ||
              (low <= lbands[j] && rbands[j] <= upp)){
            low = min(lbands[j], low);
            upp = max(rbands[j], upp);
          }else{
            if (!pushed && upp < lbands[j]){
              pushed = true;
              lbands2.push_back(low);
              rbands2.push_back(upp);
            }
            lbands2.push_back(lbands[j]);
            rbands2.push_back(rbands[j]);
          }
        }
        if (!pushed){
          lbands2.push_back(low);
          rbands2.push_back(upp);
        }
        lbands = lbands2;
        rbands = rbands2;
      }
      int res = 0;
      for(i = 0; i < lbands.size(); i++){
        res += max(0, rbands[i] - max(9001, lbands[i]) + 1);
      }
      return res;
    }
};

改善版

class Over9000Rocks
{
public:
  int countPossibilities(vector <int> lowerBound, vector <int> upperBound)
    {
      set<int> vs;
      int i, j;
      int n = lowerBound.size();
      vector<pair<int, int> > bands;
      for(i = 1; i < (1 << n); i++){
        pair<int, int> lu;
        lu.first = 0;
        lu.second = 0;
        for(j = 0; j < n; j++) if ((i >> j) & 1){
            lu.first += lowerBound[j];
            lu.second += upperBound[j];
          }
        bands.push_back(lu);
      }
      sort(bands.begin(), bands.end());
      int l = 0;
      int u = 0;
      int res = 0;
      for(i = 0; i < bands.size(); i++){
        if (bands[i].first <= u){
          u = max(u, bands[i].second);
        }else if (u < bands[i].first){
          res += max(0, u-max(9001,l)+1);
          l = bands[i].first;
          u = bands[i].second;
        }
      }
      res += max(0, u-max(9001,l)+1);

      return res;
    }
};