TopCoder SRM 726 Div2 Hard: HeroicScheduled2

するめうめ

tsutaj.hatenablog.com

問題

原文 → TopCoder Statistics - Problem Statement

個の仕事があり、それぞれについてこなすために の時間がかかり、その仕事を実行できる時間が区間として決まっている。

個の仕事の部分集合であって、適切にこなすことで全タスクをこなせるような部分集合の総数を求めよ。

解説

貪欲込みの DP で解きました。

すでに仕事を割り当てた時間の集合が であるような部分集合の総数 とします。何も考えずに DP を組むと、例えば S = 11 (binary) のときに、仕事 を 番目に割り当て、仕事 を 番目に割り当てたときの状態と、仕事 を 番目に割り当て、 仕事 を 番目に割り当てる場合を別々に数えてしまいます。これでは答えが合わないので、もう少し工夫する必要があります。

ここで、区間スケジューリングと同じように、それぞれの仕事の区間を終端でソートします。さらに、選べる時間の中で最も早いところを選択するようにします。そうすることで重複がなくなり、正しく数えられます。

ソースコード

const int itrvl = 16;
long long int dp[1 << itrvl];

struct Segment {
    int l, r;
    bool operator<(const Segment &s) const {
        if(r != s.r) return r < s.r;
        return l < s.l;
    }
};

class HeroicScheduled2 {
    public:
    long long getcount(vector<int> start, vector<int> finish) {
        int N = start.size();
        vector<Segment> seg;
        for(int i=0; i<N; i++) {
            seg.push_back(Segment{start[i], finish[i]});
        }
        sort(seg.begin(), seg.end());

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int i=0; i<N; i++) {
            for(int bit=(1<<itrvl)-1; bit>=0; bit--) {
                for(int k=seg[i].l; k<=seg[i].r; k++) {
                    if(bit >> k & 1) continue;
                    dp[bit | (1 << k)] += dp[bit];
                    break;
                }
            }
        }
        long long int ans = accumulate(dp, dp+(1<<itrvl), 0LL);
        return ans;
    }
};