Car-pal Tunnel [February Challenge 2018 D]

https://www.codechef.com/FEB18/problems/CARPTUN

N本のトンネルとC台の車がある。
車の速さは毎秒Sメートルで、トンネル間の長さはDメートル。
各トンネルではA[i]秒だけ待たされる。
車はC台順番に出発し、追い抜かすことはできない。
最初の車が到着してから、最後の車が到着するまでにかかる時間は？

解法

https://www.codechef.com/FEB18/problems/CARPTUN

まだ1000人以上解いているので、そんなにややこしくならないだろうという想像ができる。
複雑な状態になりそうにならないので、簡単になるべく考えてみる。
すると、次の性質に気付く
「最後に渋滞した所で到着の時間差が分かる」
渋滞しなければ、かかる時間の差は変化しないので、最後に渋滞した所を特定したい。
　
これにはシミュレーションしよう。
C台全てではなく、最初の2台だけでシミュレーションする。
もし、2台目が1台目を待つ状況になれば、残り全ても待つはずだからである。
　
最後に渋滞した所をrootとすると、最初の車が渋滞を抜け出してから、最後の車が渋滞を抜け出すまでA[root] * (C-1)秒かかるので、これを答える。
小数はフェイク。

#define EPS 1e-10
int N, A[101010];
double C, D, S;
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cin >> C >> D >> S;
 
    int root = 0;
    double top = 0, sec = 0;
    rep(i, 0, N) {
        top += A[i];
        if (sec <= top + EPS) {
            root = i;
            top = A[i] + D / S;
            sec = A[i] * 2 + D / S;
        } else {
            top += D / S;
            sec += A[i] + D / S;
        }
    }
 
    double ans = A[root] * (C - 1);
    printf("%.10f\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T;  cin >> T;
    rep(t, 0, T) solve();
}