SRM 539 Div2 500 Over9000Rocks

問題概要

n個の箱がある。この中からいくつかの箱を選んで石を入れたい。

ただしそれぞれの箱には入れる石の下限と上限が決められており、その箱を選んだ場合は[下限, 上限]の個数の石を入れないといけない。

• X > 9000
• いくつかの箱を選んで石をいれたときに、入れた石の合計個数がXになる

という条件を満たすようなXの個数を求めよ。

ただし、入力値は以下の条件を満たす。

1 <= n <= 15

1 <= 下限値 <= 1,000,000

対応する下限値 <= 上限値 <= 1,000,000

解き方

まず選ぶ箱の集合を全列挙する。

箱の集合が決まれば、選んだ集合にいれることのできる石の合計値の下限、上限が求まる。あとは、この下限から上限までの範囲の値が選べるということを記憶するためのデータ構造があればよい。

div2 500で遅延セグ木書かせるのか。もっと楽な方法があるはず。と思って、そういば「いもす法」ってやつがあるのを思い出して書いてみた。

コード

「いもす法」便利。

上位陣の人は+/-されるところの点をmapで管理して書いていた。
自分のはint16_tでメモリ制限ぎりぎりセーフ解。

int16_t imos[15000010];

class Over9000Rocks {
  public:
  int countPossibilities(vector<int> lb, vector<int> ub) {
    memset(imos, 0, sizeof(imos));

    int n = lb.size();
    REP (mask, 1<<n) {
      if (!mask) continue;
      int l = 0;
      int r = 0;
      REP (i, n) {
        if (mask & 1 << i) {
          l += lb[i];
          r += ub[i];
        }
      }
      imos[l]++;
      imos[r+1]--;
    }

    int ret = 0;
    int cur = 0;
    FOR (i, 1, 15000010) {
      cur += imos[i];
      if (cur > 0 && i > 9000)
        ++ret;
    }
    
    return ret;
  }
};