SRM 502 div1 med:TheProgrammingContestDivOne

問題

TopCoder Statistics - Problem Statement

解法

普通に調べようとすると多分思いつくのはO(n * 2^n)の動的計画法です。しかしこれでも計算量が多すぎるので更に工夫が必要です。

そこで,少し別の問題を考えてみます：
仮に解く問題が決まっているとすると,どのような順番で解くべきか？・・・(＊)

この問題を解くことのできるような「基準」が出来たとすると,問題を解く優先順位順に問題を並べて,
dp[n][t] := (n問目の時点で残り時間がtの時得ることのできる最高得点)
というdpを考えて問題を解くことが出来ます。

では(＊)を考えてみます。
ある2つの問題p, qのどちらを先に解くべきかを考えます。すなわち,

①..., p, q, ...
②..., q, p, ...

の2つを考えたとすると,どちらのほうが点数が高いか,ということを考えます。以下maxPointをmp, pointsPerMinuteをppm, requiredTimeをrtと略記します。それぞれの場合の得点は,

①-> mp[p]-ppm[p]*rt[p] + mp[q]-ppm[q]*(rt[p]+rt[q])
②-> mp[q]-ppm[q]*rt[q] + mp[p]-ppm[p]*(rt[p]+rt[q])
(p, qを解き始める前のオフセットは除いています)

①-②-> ppm[p]*rt[q] - ppm[q]*rt[p]

よって,pのほうが優先すべきの場合,

ppm[p]*rt[q] >= ppm[q]*rt[p]

が成り立っているとわかります。

以下ソースコード

struct problem {
    ll mp;
    ll ppm;
    ll rt;
    problem() {}
    problem(int a, int b, int c) : mp(a), ppm(b), rt(c) {}
    bool operator<(const problem& rhs) const {
        return rt*rhs.ppm < rhs.rt*ppm;
    }
};

const int MAXT = 100100;
const int MAXN = 55;
ll dp[MAXN][MAXT];

class TheProgrammingContestDivOne {
public:
    int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
        int n = maxPoints.size();
        vector<problem> ps(n);
        for (int i = 0; i < n; i++) {
            ps[i] = problem(maxPoints[i], pointsPerMinute[i], requiredTime[i]);
        }
        sort(ps.begin(), ps.end());
        memset(dp, -1, sizeof(dp));
        dp[0][T] = 0;
        for (int i = 0; i < n; i++) {
            for (int t = T; t >= 0; t--) {
                if (dp[i][t] == -1) continue;
                dp[i+1][t] = max(dp[i+1][t], dp[i][t]);
                if (t >= ps[i].rt) {
                    ll point = dp[i][t];
                    point += ps[i].mp - ps[i].ppm*((T-t)+ps[i].rt);
                    dp[i+1][t-ps[i].rt] = max(dp[i+1][t-ps[i].rt], point);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i <= T; i++) {
            ans = max(ans, (int)dp[n][i]);
        }
        return ans;
    }
};

これのdiv2バージョンを本番16秒で解いてる人がいるらしいですが人間じゃないなぁと思いますね。