けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

キーエンス プログラミング コンテスト 2020 B - Robot Arms (200 点)

区間スケジューリング問題そのものだった!!!
...とはいえ 200 点というのは衝撃!!!

問題へのリンク

問題概要

ある工場では、 数直線上に  N 個のロボットが設置されている。 ロボット  i は座標  X_{i} に設置されていて、左右に長さ  L_{i} のアームを伸ばしている。

これらのロボットのうちいくつかを取り除き、 残ったどの 2 つのロボットについても、アームが共通部分を持たないようにしたい。取り除かずに残せるロボットの個数の最大値を求めよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

つまり、以下の  N 個の区間についての、区間スケジューリング問題 (蟻本参照) ということになる。

  •  (X_{0} - L_{0}, X_{0} + L_{0})
  •  (X_{1} - L_{1}, X_{1} + L_{1})
  • ...
  •  (X_{N-1} - L_{N-1}, X_{N-1} + L_{N-1})

区間スケジューリング問題とは、いくつかの区間の中から、重ならないように最大で何個選べるかを問う問題である。

区間スケジューリング問題の解き方

区間を「終端が早い順」にソートして、とれる順にとる Greedy で解くことができる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    int N; cin >> N;
    vector<pll> v(N);
    for (int i = 0; i < N; ++i) {
        long long a, l;
        cin >> a >> l;
        v[i] = {a - l, a + l};
    }

    // 区間を右端の小さい順にソート
    sort(v.begin(), v.end(), [](pll a, pll b) {
            return a.second < b.second;});

    // cur := 現在選んでいる区間のうち、最も右にあるやつの右端
    int res = 0;
    long long cur = -(1LL<<60);
    for (int i = 0; i < N; ++i) {
        if (cur > v[i].first) continue; // 被るやつは飛ばす
        ++res;
        cur = v[i].second;
    }
    cout << res << endl;
}