As Fast As Possible [Codeforces 364 : Div2 D, Div1 B]

問題

http://codeforces.com/contest/701/problem/D

n人の生徒がいて、距離lを移動する。
生徒が普通に移動すると速さv1。
バスを使って移動すると速さv2。
各生徒バスには1回しか乗らない。
バスは一度にk人しか乗せられない。
バスをうまく使ったとき、n人全員が移動する最短時間は？

※バスは1台しかなく、他の生徒が使うときはそこまでバスを移動させる時間も考えなくてはならない（！！！）

1 <= n <= 10^5
1 <= l <= 10^9
1 <= v1 < v2 <= 10^9
1 <= k <= n

考察

1. これは数学ゲーだなという印象で取り組んでいました
2. まずn人いて、k人バス乗れるのでd=ceiling(n/k)グループできる
3. dグループがみな、同じような行動をとるだろうなという予想（均衡点的な）
4. この予想を元に考えて、考えて、考えて…

この辺を言葉で説明するの無理じゃない？
とりあえず、バスに乗る時間を一律 x 時間とおいて、方程式やらなにやら作ってると計算式が作れました。
あとは、誤差との勝負ですが、double入れまくってビビりながら提出しましたが、system check耐えてくれて安心です

5. 導出式については実装を参照で

実装

http://codeforces.com/contest/701/submission/19344104

int n, l, v1, v2, k;
//-----------------------------------------------------------------
int main()
{
	cin >> n >> l >> v1 >> v2 >> k;

	int d = n / k;
	if (n % k != 0) d++;

	double x = (double)l * (double)(1.0 + (double)v1 / (double)v2) / (double)((double)v2 - (double)v1 + 2.0 * (double)v1 * (double)d);
	double xx = x * (double)((double)v2 - (double)v1) / (double)((double)v2 + (double)v1);
	double ans = x * (double)d + xx * (double)(d - 1);

	printf("%.10f\n", ans);
}