mayoko’s diary

プロコンとかいろいろ。

SRM 539 div1 easy: Over9000Rocks

解法

選ぶグループを決めればその箱のグループで得られる石の最小値, 最大値がわかります。得られる石の数は明らかに連続に取れるので, mp という配列を用意して, mp[最小値] = (最大値) となるようにしておきます。複数のグループで同じ最小値を取ることがありあますが, その時は最大値が大きい方を保持しておきます。

で, 後はこの配列の情報をもとに石の数の場合の数を数え上げれば良いだけです。最小値 lp が小さい順に配列を見ていき, 今までの配列の値の最大値("最大値"の最大値) を rp とします。

  • rp < lp のとき, mp[lp]-lp+1 を足す
  • lp < rp < mp[lp] のとき, mp[lp]-rp を足す

ということを繰り返せば良いです。mp 配列はそのまま取ると MLE するので, map などを使って座標圧縮します。

class Over9000Rocks {
public:
    int countPossibilities(vector <int> lb, vector <int> ub) {
        map<int, int> mp;
        int n = lb.size();
        for (int s = 0; s < (1<<n); s++) {
            int mini = 0, maxi = 0;
            for (int i = 0; i < n; i++) if ((s>>i)&1) {
                mini += lb[i]; maxi += ub[i];
            }
            if (maxi <= 9000) continue;
            mini = max(mini, 9001);
            mp[mini] = max(mp[mini], maxi);
        }
        int ret = 0, rp = -1;
        for (auto it = mp.begin(); it != mp.end(); it++) {
            if (rp < it->first) {
                ret += it->second - it->first + 1;
                rp = it->second;
            } else {
                if (it->second > rp) {
                    ret += it->second - rp;
                    rp = it->second;
                }
            }
        }
        return ret;
    }
};