CODE FESTIVAL 2017 Final: D - Zabuton

,

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_d

正当性の証明についてhamkoさんと議論した。 editorialは読めば分かった気にはなれる(当然)のだが、もうちょっと厳密で一般的なところが気になる。 私に関しては貪欲法に関する証明のまわりが弱いので不安感が生じているはずで、マトロイドとか離散凸解析とかそのあたりをするべきなのだろうなという思いになって終わった。

solution

見る順序は$H_i + P_i$の順のみでよい。この順に$i$番目まで見て$j$個取ったときの高さの最小値を$\mathrm{dp}(i, j)$としてDP。$O(N^2)$。

スケジューリング問題と見るのが楽という指摘もあった:

implementation

#include <algorithm>
#include <cstdio>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr ll inf = ll(1e18)+9;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<pair<int, int> > hps(n);
    repeat (i, n) {
        int h, p; scanf("%d%d", &h, &p);
        hps[i] = { h, p };
    }
    // solve
    sort(whole(hps), [&](pair<int, int> hp1, pair<int, int> hp2) {
        return hp1.first + hp1.second < hp2.first + hp2.second;
    });
    vector<ll> dp(n + 1, inf);
    dp[0] = 0;
    for (auto hp : hps) {
        int h, p; tie(h, p) = hp;
        repeat_reverse (j, n) {
            if (dp[j] <= h) {
                setmin(dp[j + 1], dp[j] + p);
            }
        }
    }
    int result = 0;
    repeat (i, n + 1) {
        if (dp[i] < inf) {
            result = i;
        }
    }
    // output
    printf("%d\n", result);
    return 0;
}