mayoko’s diary

プロコンとかいろいろ。

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

これも問題文長い…