SRM 307 Div1 Medium TrainRobber

問題

電車がx軸正方向に速さtrainSpeedで動いている。電車は車両数がnCarriagesで車両の長さはいずれもlengthである。時刻0の時点では電車の左端が座標0に位置している。この左端に強盗が立っており、時刻0になると電車の屋根の上を速さrobberSpeedで右端に向かって走りだす。線路はいくつかの架橋の下を通っており、強盗は橋を通過する時に屋根の上にいることはできず、車両と車両の間にいなければならない。橋は最初にoffsetの位置に現れ、その後periodごとに現れる。（表現方法はめんどうなので問題文参照）
強盗はなるべく早く右端に行こうとするが、その前にnBridges個の橋を通過してしまった場合にはその時点で右端に行くことを諦める。
強盗が右端についた時か、もしくは右端に行くことを諦めた時にx座標上で彼がいた地点を求めよ。

やりかた

一つ一つ考える。
ある橋を通過した時に強盗がいる地点をposとし、次の橋の位置をnextとすると、強盗がposからnextに行くまでにかかる時間Tは (next - pos) / (trainSpeed + robberSpeed) になる。
ところで強盗が車両1つ分を移動する時間tは length / robberSpeed である。
なのでposからnextに至るまでに強盗が通過できる車両数は
floor(T / t) = floor((next - pos) * robberSpeed / (trainSpeed + robberSpeed) / length)
nBridges個の橋の下を通る前にこれらの和がnCarriagesを超えれば強盗は無事右端に辿りつけたことになる。
ここである橋(pos)を通って次の橋(next)までの間に右端に行き着くケースを考える。posの時点で残りの車両数がQ個だったとする。すると強盗が残りのQ車両を全部渡るには Q * length / robberSpeed だけかかる。この間に強盗は地面に対してrobberSpeed + trainSpeed の速さで動くので、渡りきった時には絶対的な位置として
pos + Q * length / robberSpeed * (robberSpeed + trainSpeed)にいることになる。

次に現れる橋を計算する方法はコードを参考。

以下ソース。

class TrainRobber {
public:
  vector<int> dec(vector<string> s){
    vector<int> ret;
    for(int i = 0; i < (int)s.size(); i++){
      stringstream ss(s[i]);
      int x;
      while(ss >> x) ret.push_back(x);
    }
    return ret;
  }
  double finalPosition(int length, int nCarriages, vector <string> offset, vector <string> period, int trainSpeed, int robberSpeed, int nBridges){
    vector<int> off = dec(offset), per = dec(period);
    set<pair<ll, int>> B;//(橋の位置、橋の種類)を持つ。橋の位置順にソートされる
    for(int i = 0; i < (int)off.size(); i++)
      B.insert(make_pair(off[i], i));
    
    ll pos = 0;
    
    for(ll i = 0; i < nBridges; i++){
      ll next = (*B.begin()).first;
      ll idx = (*B.begin()).second;
      B.erase(B.begin());//通過した橋は消す
      ll p = (next - off[idx]) / per[idx] + 1;//この種類の橋はいくつ通過したか
      B.insert(make_pair(off[idx] + per[idx] * p, idx)); //この種類の橋の（次の位置、種類）を記憶

      ll t = (next - pos) * robberSpeed / ((ll)length * (trainSpeed + robberSpeed));
      //渡りきった場合の位置
      if(t >= nCarriages) return pos + 1.0 * nCarriages * length * (robberSpeed + trainSpeed) / robberSpeed;
      nCarriages -= t;
      pos = next;
    }
    return pos;//諦めた場合の位置
  }
};

橋を通過する部分でdoubleを使って少数同士の計算をしていたがどうしても誤差死を免れないケースがあった。なんとか整数帰着して解いた。