SRM 235 DIV1 Hard RemoteRover
問題
水平の境目で分割された領域がいくつかある。
それぞれの領域は幅がwidth[i]で、speed[i]の速度を出すことができる。
(0, 0)から(offset, sum width)まで行くとき、時間を最小化せよ
解答
それぞれの領域ではspeed[i]に比例する傾き(cosθ)で行けばいい。
なぜかはわかってないが、そうらしい。
あとは比例の係数を求めたいが、二分探索でいい
コード
#include <vector> #include <algorithm> #include <cmath> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(o) (o).begin(), (o).end() using namespace std; typedef long double ld; struct RemoteRover { double optimalTravel(vector <int> width, vector <int> speed, int offset) { int n = width.size(); ld l = 0, u = 1.L / *max_element(all(speed)); ld d; rep(ii, 100) { ld m = (l+u)/2; ld x = 0; d = 0; rep(i, n) { ld s = acos(speed[i] * m); x += width[i] / tan(s); d += width[i] / sin(s) / speed[i]; } if(x > offset) u = m; else l = m; } return d; } };