TopCoder SRM 307 Div1 Medium TrainRobber

問題

n両の客車からなる電車がある。
一両の長さはlengthで、時刻0に電車の左端がx=0に位置している。
電車は数直線の正の向きに、trainSpeedで移動している。


泥棒が電車の左端から右端へ移動したい。
泥棒が移動する速度はrobberSpeedである。


線路には橋があり、電車が橋を通過するときは、泥棒は客車と客車の間もしくは、電車の両端にいなければならない。
橋はの座標は、offsetとperiodによって与えられ、
i番目の橋の列はoffset[i]+period[i]*k(ただしkは0以上の整数)のx座標の位置にあり、
全ての橋の列を合わせたものが線路に現れる橋である。


泥棒が、nBridge個の橋を通過する時刻と、電車の右端に辿り着く時刻の早いほうの時刻における、
泥棒のx座標を求めよ。

制約条件

length≦1000000
nCarriages≦1000000
offsetとperiodは長さ2500以下の文字列で与えられる。
offset, period≦1000000
trainSpeed, robberSpeed≦1000000
nBridges≦1000000

方針

シミュレート。
次の橋が来るまでの間に、客車をどれだけ移動できるかを二分探索する。
これをnBridges回繰り返す。


途中で、客車を全て渡りきったら、その時点でのx座標を返す。


次の橋の座標を求めるのは、priority_queueを使えばよい。
priority_queueに座標と橋が何番目の列で生成されたものかを表す番号を入れておいて、
キューから取り出されたときに、同じ列の次の橋をキューに入れるようにする。

ソースコード

class TrainRobber {
  public:
  double finalPosition(int length, int nCarriages, vector <string> offset, vector <string> period, int trainSpeed, int robberSpeed, int nBridges) {
    
    vi o,p;
    
    string s,t;
    rep(i,offset.size())s+=" "+offset[i];
    rep(i,period.size())t+=" "+period[i];
    stringstream ss(s), tt(t);
    int x;
    while(ss>>x)o.pb(x);
    while(tt>>x)p.pb(x);
    
    int n=o.size(), car=0;
    
    priority_queue<pair<double,int> > q;
    rep(i,n)q.push(mp(-o[i],i));
    double pos=0;
    
    rep(it,nBridges){
      double x=-q.top().first;
      int id=q.top().second;
      q.push(mp(-x-p[id], id));
      q.pop();
      
      int lo=car, hi=nCarriages+1, mid;
      while(lo+1<hi){
        mid=(lo+hi)/2;
        double t=(mid-car)*1.0*length/robberSpeed;
        if(t*trainSpeed+(mid-car)*1.0*length<x-pos+EPS)lo=mid; else hi=mid;
      }
      if(lo==nCarriages){
        double t=(lo-car)*1.0*length/robberSpeed;
        return pos+(lo-car)*1.0*length+t*trainSpeed;
      }
      pos=x;
      car=lo;
    }
    return pos;
  }
};