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(); }