LoginSignup
1
0

More than 3 years have passed since last update.

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

Posted at

対象の問題

キーエンス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; //残した数を提出
}
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0