https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b
前提知識
解説
https://atcoder.jp/contests/keyence2020/submissions/9582655
DPをしよう。
200点でなので想定解は貪欲なんだろうという気もするが、DPでさくっとかけるので書いてしまう。
dp[i] := i番目まで残すか確定していて、i番目のロボットを残した場合の個数最大値
どうやってこれで解くんだろうというのを説明する。
ロボットを左から残していくかを考えると、i番目のロボットを置くと、X[i]+L[i]-1までは占領してしまう。
かつ、i番目のロボットがおけるのは、最後にロボットとその手がかかる領域がX[i]-L[i]までの場合である。
これは既に置かれているロボットのX[i]+L[i]-1が関係してくる。
つまり、順番はX[i]+L[i]の昇順に置かれることになる。
よって、これでソートしておくと、順番に置くかどうかの問題となり、DPに帰着させることができる。
dp[i+1]を更新したい時に、i番目のロボットがおけるかを考えたいが、lower_boundを使って、pre番目のロボットまでおけることを調べよう。
すると、dp[i+1]はmax(dp[0], dp[1], ..., dp[pre]) + 1となるが、計算しながら、
dp[i] := i番目まで残すか確定している場合の個数最大値
を累積和っぽく求めておくと、達成できる。
追記:区間スケジューリング問題でしたね。ホントやわ。
{ X[i]+L[i], X[i]-L[i] }で配列入れて、ソートして、区間の右端が小さいものから貪欲に取って、カウントしていく。
int N; pair<int, int> robots[101010]; int dp[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) { int x, l; cin >> x >> l; robots[i] = { x + l, l }; } sort(robots, robots + N); rep(i, 0, N) { chmax(dp[i + 1], dp[i]); int x = robots[i].first - robots[i].second; int l = robots[i].second; auto ite = lower_bound(robots, robots + N, make_pair(x - l, inf)); int pre = ite - robots; chmax(dp[i + 1], dp[pre] + 1); } cout << dp[N] << endl; }