【ICPC World Final 2017】E : Need for Speed

問題

Need for Speed – Kattis, ICPC

• ある区間の距離と移動速度がそれぞれとして与えられる.
• は実際の速度s+c(cは定数)として表示されている.
• 実際にかかった時間tが与えられるので, cが何であるかを求めよ.

方針

• となったときのCが答えとなる.
• 二分探索を行い, Cを試して答えを求める.
• 区間の設定が重要で, sの最小値から[tex: {10⁶+1000}]までの区間で二分探索した.

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define eps 1e-14

using namespace std;

signed main(){
  int n;
  double t;
  double d[1001], s[1001];
  double _min = 1500.0, _max = -1200;

  scanf("%d %lf", &n, &t);
  rep(i, n){
    scanf("%lf %lf", &d[i], &s[i]);
    _min = min(s[i], _min);
  }
  
  double right = _min; 
  double left = -1001000;
  double c;
  double prev = 0.0;
  
  rep(i, 100){  
    c = (left + right)/2.0;
    double sum = 0.0;
    rep(i, n) sum += (d[i] / (s[i] - c));  
    if(fabs(sum - t) < eps){
      break;
    }else if(sum > t){
      right = c;
    }else{
      left = c;
    }
    prev = sum;
  }
  printf("%.9f\n", -c);
}
``