TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

画像がついてるので分かりやすい．$1$つの車両の長さが$length$で，それが$nCarriages$車両ある．車両の上の一番左からスタートして，車両の一番右に到達したいが，橋を通過するときは車両の上にいることが出来ない．$nBridges$通過時点でどこにいるか求める．

橋の入力が空白区切りかつ複数の文字列で与えられるので面倒．次に来る橋をpriority_queueで管理する．
次の橋までの時間を$s$，$1$車両移動する時間を$t$と置くと以下のようになる．

$$ \begin{eqnarray} s &=& \frac{next - cur}{robberSpeed + trainSpeed} \\ t &=& \frac{length}{robberSpeed} \end{eqnarray} $$

$\frac{s}{t}$が次の橋が来るまでに行ける車両の個数となるが，このまま計算すると誤差で死ぬので $$ \frac{(next - cur) \times robberSpeed}{(robberSpeed + trainSpeed) \times length} $$ の形にするが，この形にすると掛け算が入るので$long long$にしないとオーバーフローする．
このままちょうど橋のところで右端までに近づければいいが，そうでない場合は地面に対する車両の右端の座標を求める必要がある． $$ \begin{eqnarray} 右端までに行く時間 & = & \frac{残りの車両 \times length}{robberSpeed} \\ & = & \frac{(nCarriages - cnt) \times length}{robberSpeed} \\ 車両の右端 & = & 右端まで行く時間 \times (robberSpeed + trainSpeed) \\ & = & \frac{(nCarriages - cnt) \times length \times (robberSpeed + trainSpeed)}{robberSpeed} \end{eqnarray} $$

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<double, int> P;

vector<string> split(const string &str, char delim) {
  vector<string> res;
  size_t current = 0, found;
  while((found = str.find_first_of(delim, current)) != string::npos) {
      res.push_back(string(str, current, found - current));
      current = found + 1;
  }
  res.push_back(string(str, current, str.size() - current));
  return res;
}

class TrainRobber {
  public:
  double finalPosition(int length, int nCarriages, vector <string> offset, vector <string> period, int trainSpeed, int robberSpeed, int nBridges) {
      vector<double> off, per;
      rep(i, offset.size()) {
          vector<string> ret = split(offset[i], ' ');
          rep(j, ret.size()) {
              double x;
              stringstream ss(ret[j]);
              ss >> x;
              off.push_back(x);
          }
      }

      rep(i, period.size()) {
          vector<string> ret = split(period[i], ' ');
          rep(j, ret.size()) {
              double x;
              stringstream ss(ret[j]);
              ss >> x;
              per.push_back(x);
          }
      }

      priority_queue<P, vector<P>, greater<P> > que;
      rep(i, off.size()) {
          que.push(mp(off[i], i));
      }

      int cnt = 0;
      double cur = 0;

      rep(i, nBridges) {
          P p = que.top(); que.pop();
          double next = p.first;
          int id = p.second;

          // double s = (next - cur) / (robberSpeed + trainSpeed);
          // double t = (double)length / robberSpeed;
          // int tmp = s / t;
          int tmp = ll(next - cur)  * robberSpeed / (length * ll(robberSpeed + trainSpeed));
          if(cnt + tmp >= nCarriages) {
              double len = (nCarriages - cnt) * length;
              return cur + len / robberSpeed * (robberSpeed + trainSpeed);
          }

          cur = next;
          cnt += tmp;
          que.push(mp(next + per[id], id));
      }

      return cur;
  }
};

ry0u_ydのblog

SRM307 D1M TrainRobber

TopCoder Statistics - Problem Statement

Code