Yandex.Algorithm 2015 Round 2.2 B問題 - Chariot Racing

Source

Yandex.Algorithm 2015
Yandex.Algorithm 2015 Round 2.2
問題文

問題概要

無限に長い $1$ 次元の直線上を $N$ 台の車が走っている.
各車には幅があり,車 $k$ は時間 $0$ では $[A_k, B_k]$ の区間におり,スピード $V_k$ で走っている.
時間 $t$ において,区間 $[l,r]$ には全ての車がいるという区間のうち最大の長さのものの長さ(そのような区間がないなら $0$)を $f(t)$ として,$t \geq 0$ における $f(t)$ の最大値を求める問題.

解法

車は速さでソートして,全て車 $1$ からの相対速度で考えることにしておく.
すると,車 $1$ は止まっており,他の車は正の方向に進むことになる.
まず,全ての車が重なっている区間がある時間の範囲の下限と上限を二分探索で求めた.
それは,車 $1$ を基準として,完全に負の方向にある車があるなら,より後の時間でないと全ての車が重なっていないとして,完全に正の方向にあるなら,より前の時間でないと全ての車が重なっていないとする.
その後は,全ての車が重なっている区間の長さの最大値を三分探索で求めた.
同じスピードのある車があっても,実装によっては何も考えなくてもうまくいく.
もしくは,同じスピードの車があるなら,全ての同じスピードの車が重なっている区間のみの車 $1$ 台に最初に置き換えてしまえば良い.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T1, class T2, class T3> void sort(int N, T1 a[], T2 b[], T3 c[], void *mem){int i;pair<T1,pair<T2,T3> > *r=(pair<T1,pair<T2,T3> >*)mem;rep(i,N)r[i].first=a[i],r[i].second.first=b[i],r[i].second.second=c[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second.first,c[i]=r[i].second.second;}

char memarr[17000000]; void *mem = memarr;
#define MD 1000000007

int N;
int A[111111], B[111111], V[111111];

int chk(double t){
  int i, fg = 0;
  double L, R, LL, RR;

  L = A[0]; R = B[0];
  REP(i,1,N){
    LL = A[i] + t * V[i];
    RR = B[i] + t * V[i];
    if(RR < L){ fg |= 1; continue; }
    if(LL > R){ fg |= 2; continue; }
    L = max(L, LL);
    R = min(R, RR);
  }
  return fg;
}

double get_len(double t){
  int i;
  double L, R, LL, RR;

  L = A[0]; R = B[0];
  REP(i,1,N){
    LL = A[i] + t * V[i];
    RR = B[i] + t * V[i];
    L = max(L, LL);
    R = min(R, RR);
  }
  return R - L;
}

int main(){
  int i, k, loop;
  double AA, BB, CC, C1, C2, D1, D2;
  double X, Y;

  reader(&N);
  rep(i,N) reader(A+i,B+i,V+i);
  sort(N, V, A, B, mem);
  REP(i,1,N) V[i] -= V[0]; V[0] = 0;

  AA = 0;
  BB = 1e10;
  rep(loop,200){
    CC = (AA+BB) / 2;
    k = chk(CC);
    if(k==3){ writerLn(0); return 0; }
    if(k==1){ AA = CC; continue; }
    if(k==2){ BB = CC; continue; }
    if(k==0){ BB = CC; continue; }
  }
  X = AA;

  AA = 0;
  BB = 1e10;
  rep(loop,200){
    CC = (AA+BB) / 2;
    k = chk(CC);
    if(k==3){ writerLn(0); return 0; }
    if(k==1){ AA = CC; continue; }
    if(k==2){ BB = CC; continue; }
    if(k==0){ AA = CC; continue; }
  }
  Y = AA;

  rep(loop,200){
    C1 = (X+X+Y) / 3;
    C2 = (X+Y+Y) / 3;
    D1 = get_len(C1);
    D2 = get_len(C2);
    if(D1 < D2) X = C1; else Y = C2;
  }

  writerLn(D1);

  return 0;
}

Current time: 2017年11月18日04時26分51秒
Last modified: 2015年06月28日03時34分01秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2015 Yandex_Algorithm_2015_Round22
トップページに戻る

Logged in as: unknown user (not login)

ログイン: