振り返り Atcoder キーエンス2020 B問題

対象の問題

キーエンス2020 B - Robot Arms

参考にさせて頂いた解法

公式解説
Derekさんの提出結果

考え方

• 右端が一番左に位置するものを残していけばよい（区間スケジューリング問題というらしい）

解法の大まかな流れ

1. pairを用いてfirstに右端（x+l),secondに左端(x-l)をいれる。
2. 1の1組を1つの要素としてvectorにいれる。
3. 右端が左に位置するものの順に(=first順で昇順に)ソートする
4. ソートした順に現在地(最初は極小の値)と左端を比べて、左端の方が現在地よりも左側にあるのならば残さない。そうでないならば(左端が現在地から右側にあるならば)残して、現在地を残した右端にする

解説のコードにコメント追記

derekさんの提出コードをベースにコメントを追記

# include <map>
# include <iostream>
# include <algorithm>
# include <vector>
# define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int n,ans = 0;
int now = -2e9; //極小な値で初期化
vector<pair<int,int>> v;

int main(){
 cin >> n;
 rep(i,n){
   ll x,l = 0; cin >> x >> l;
   v.push_back(make_pair(x+l,x-l)); //右端をfirst,左端をsecondとして要素を追加していく
 }

 sort(v.begin(),v.end()); //first,secondの昇順でソート

 rep(i,n){
   if(v[i].second < now){
     continue; // 左端が現在地よりも左側ならば残さない
   }
   else{ //そうでないならば現在地を右端にして残す
     now = v[i].first;
     ans++;
   }
 }
 cout << ans; //残した数を提出
}