AtCoder Regular Contest 008 C - THE☆たこ焼き祭り2012

最近 Splatoon の病に陥っているので「たこ焼きを投げる」と言われるとイカがボムを投げてる姿が思い浮かぶ。

問題

arc008.contest.atcoder.jp

解法

問題の様子を見ます。

点(x0, y0) の人を 0, 点(x1, y1) の人を 1, ..., 点(xn, yn) の人を n とします。
まず気づくのは, 0 の人は必ず n-1 回たこ焼きを投げないといけないということです。つまり, すべての人にたこ焼きが行き渡るためには少なくとも n-1 秒かかります。

なので, イメージとしては時間がかかる人にはなるべく早くたこ焼きをお届けするのが有利です。とりあえずこれを最短経路問題として解いてみましょう。これはダイクストラのアルゴリズムを使えば簡単です。
で, 実はこの最短経路の短い人には n-2 秒後にたこ焼きを届けて始めて, 次に短い人には n-3 秒後に届けて始めて, ... 一番経路の長い人には 0 秒後にたこ焼きを届け始めて, とすると良くて, これが解法になります。なぜこれで大丈夫なのかを考えてみます。

少し話がずれますが, ダイクストラのアルゴリズムでは, 「最適性原理」と呼ばれる原理があります。
これは, s -> u への最短経路があるパス p で表される時, s から u を通して v に向かう最短経路を考えた場合, s -> u -> v のうち s -> u への経路としては p を採用するのがやはり最適, という原理です(厳かな名前がついてますがアタリマエですね)。

で, これを考えると, 0 の人以外は絶対にたこ焼きが 1 秒以上の間隔をおいてたこ焼きが投げられることがわかります。
なぜかというと, ある頂点 v を通してどこかの頂点 u にたこ焼きを運ぶ場合, 最適性原理により, s から v への経路はひとつの経路 p に限定して良いので, s がたこ焼きを 1 秒ごとに投げるという前提では, 必ずたこ焼きは 1 秒以上のスパンをおいてやってきます。

よって, 先ほどダイクストラでとりあえず求めておこうと言った最短経路は, 1 秒毎に必ず採用されます。
ということで, 各頂点へたこ焼きを届け始めた時間を t, 0 からその頂点までたこ焼きを届けるのにかかる時間を td とすると, その頂点にたこ焼きを届けるのにかかる時間は t+td で求められます。

これはちょっと考えればわかりますが, td が大きい物ほど早めに届けるほうが全員に届けるのにかかる時間は短くなります。なので, 先ほど提案した解法で答えが得られることがわかりました。

const int MAXN = 1010;
int x[MAXN], y[MAXN], t[MAXN], r[MAXN];

const double INF = 1e10;

struct edge {
    int v;
    double w;
    edge() {}
    edge(int v, double w) : v(v), w(w) {};
};

vector<double> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<double> d(n, INF); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

double dist(int x0, int y0, int x1, int y1) {
    double dx = x1-x0, dy = y1-y0;
    return sqrt(dx*dx+dy*dy);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> t[i] >> r[i];
    }
    vector<vector<edge> > G(N);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        G[i].emplace_back(j, dist(x[i], y[i], x[j], y[j])/min(t[i], r[j]));
    }
    auto d = dijkstra(N, G, 0);
    sort(d.begin(), d.end());
    double ans = 0;
    for (int i = 1; i < N; i++) ans = max(ans, d[i]+(N-i-1));
    printf("%.10lf\n", ans);
    return 0;
}