Robot Arms [Keyence Programming Contest 2020 B]

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;
}