SRM 426 div1 med:CatchTheMice
解法
定式化するのが一番大事なポイント。そこをはっきりさせればすぐに解法は3分探索だと思いつく。
この問題を定式化すると以下のようになる:
xi = xp[i] + xv[i] * t
yi = yp[i] + yv[i] * t
xj = xp[j] + xv[j] * t
yj = yp[j] + yv[j] * t
としたとき,
f(t) := (max(abs(xi-xj), abs(yi-yj)) のi=0〜n-1, j=0〜n-1まで走らせた時の最大値)
を最小化する問題になる。
f(x), g(x)が凸関数であるとした時,max(f(x), g(x))が凸関数になるということ,及びabs(a*t + b)という形の関数はtについて凸であるということを用いると,上のf(t)という関数は下に凸であるということがわかる。
よって,3分探索を用いてf(t)を最小にするtを求め,そのtにおけるf(t)の値を返せば良い。
vector<int> xp, yp, xv, yv; double evaluate(double t) { int n = xp.size(); double ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { double xi = xp[i] + xv[i] * t; double yi = yp[i] + yv[i] * t; double xj = xp[j] + xv[j] * t; double yj = yp[j] + yv[j] * t; ans = max({ans, abs(xi-xj), abs(yi-yj)}); } } return ans; } class CatchTheMice { public: double largestCage(vector <int> Xp, vector <int> Yp, vector <int> Xv, vector <int> Yv) { xp = Xp; yp = Yp; xv = Xv; yv = Yv; double low = 0, high = 2000; for (int i = 0; i < 100; i++) { double m1 = low + (high-low)/3; double m2 = low + (high-low)/3*2; double left = evaluate(m1); double right = evaluate(m2); if (left < right) high = m2; else low = m1; } return evaluate(low); } };
これも問題文長い…