CODE FESTIVAL 2017 Final: D - Zabuton
正当性の証明についてhamkoさんと議論した。 editorialは読めば分かった気にはなれる(当然)のだが、もうちょっと厳密で一般的なところが気になる。 私に関しては貪欲法に関する証明のまわりが弱いので不安感が生じているはずで、マトロイドとか離散凸解析とかそのあたりをするべきなのだろうなという思いになって終わった。
solution
見る順序は$H_i + P_i$の順のみでよい。この順に$i$番目まで見て$j$個取ったときの高さの最小値を$\mathrm{dp}(i, j)$としてDP。$O(N^2)$。
スケジューリング問題と見るのが楽という指摘もあった:
個人的には、このようなスケジューリング問題に落とせるという話が一番納得できましたhttps://t.co/LeSuktj3Eg
— りあん (@rian_tkb) 2017年11月26日
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;
}