ARC008 C問題：THE☆たこ焼き祭り2012

問題. THE☆たこ焼き祭り2012

時刻 0 に 1 番目の人から $i \,(2 \le i \le N)$ 番目の人へたこ焼きを1つ渡すことを考える． $i \, (1 \le i \le N)$ 番目の人は平面上の $(x_i, y_i)$ にいて，受け取る速度の上限が $r_i$ で，渡す速度の上限が $t_i$ である．たこ焼きの受け渡しはいくつかの人を経由してもよいが，すべての人に対してその人の渡す間隔は少なくとも 1 秒必要があり，1度に1個のたこ焼きしか渡すことができない．1 番以外のすべての人がたこ焼きを受け取るまでにかかる時間の最小値を答えよ．

制約： $1 \le N \le 1,000$ ，　 $-10,000 \le x_i, y_i \le 10,000$ ，　 $3 \le r_i, t_i \le 340$

解法．最短経路問題

「渡す間隔が少なくとも1秒必要」と「1度に1個のたこ焼きしか渡せない」という2つの制約がない場合を考える．このとき，時刻 0 に 1 番目の人から他のすべての人へ到達時刻が最小となるようにたこ焼きを経由して渡すことが最適となり，一番遅い人の到達時刻が答えとなる．1番目の人から他の人への到達時刻が最小となるような経路は時間に関しての最短経路問題を解くことによって求めることができ，ダイクストラ法を用いると $O(N \log N)$ 時間で求まる．

ここで，上の2つの制約があるときに同時にたこ焼きを受け取る可能性があるかを考える． $i$ 番目の人が $j$ 番目と $k$ 番目の人から同時刻にたこ焼きを受け取ったと仮定する．この2つのたこ焼きが1番目の人から出発した時刻は少なくとも1秒以上異なる．もし， $j$ 番目の人からのたこ焼きの方が出発時刻が早かった場合は， $k$ 番目の人の経路を使用した方が早く到達するので到達時刻最小化に矛盾する．したがって，最適解では同時に複数のたこ焼きを受け取ることはなく，また，その間隔も少なくとも1秒以上空いていることが分かる．すなわち，受け取った時刻に他の人にそのたこ焼きを渡すことが可能である．
以上から，1番目の人からの到達時刻が遅い人から順番にたこ焼きを渡すことが最適となる．

計算時間： $O(N \log N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

template<class T>
struct Graph {
    const T INF = std::numeric_limits<T>::max();
    const int n;
    int s, t;
    std::vector<std::vector<T>> adj;
    std::vector<T> d;

    Graph(int _n, int _s, int _t = -1)
        : n(_n), s(_s), t(_t), adj(n, std::vector<T>(n, INF)), d(n, INF) { }

    void add_edge(int u, int v, T w) { adj[u][v] = w; }
    T distance(const int _t) const { return d[_t]; }

    void Dijkstra() {
        std::vector<bool> used(n, false);
        d[s] = 0;
        while (true) {
            int v = -1;
            for (int u = 0; u < n; ++u)
                if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
            if (v == -1 || INF <= d[v]) break;
            // if (v == -1 || INF <= dist[v] || v == t) break;
            used[v] = true;
            for (int u = 0; u < n; ++u)
                if (adj[v][u] != INF) d[u] = std::min(d[u], d[v] + adj[v][u]);
        }
    }
};

double Solve() {
    int N;
    cin >> N;

    vector<double> x(N), y(N), t(N), r(N);
    for (int i = 0; i < N; ++i)
        cin >> x[i] >> y[i] >> t[i] >> r[i];

    if (N == 1) return 0.0;

    Graph<double> g(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;

            const double dx = x[i] - x[j], dy = y[i] - y[j];
            const double d = sqrt(dx * dx + dy * dy);
            const double v = min(t[i], r[j]);
            g.add_edge(i, j, d / v);
        }
    }

    g.Dijkstra();

    vector<double> tm(N - 1);
    for (int i = 1; i < N; ++i)
        tm[i - 1] = g.distance(i);

    sort(tm.begin(), tm.end(), greater<double>());

    double max_tm = tm[0];
    for (int i = 1; i + 1 < N; ++i)
        max_tm = max(max_tm, i + tm[i]);

    return max_tm;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(8) << setiosflags(ios::fixed);

    cout << Solve() << endl;

    return 0;
}

同時にたこ焼きを受け取らないことがミソ．