テスターしてました！難しかった。

問題へのリンク

問題概要

ラスク君は木を持っていましたが、なくしてしまいました。

この木は、頂点に 1 以上頂点数以下の相異なる整数の番号がついていて、各辺には $1$ 以上 $10^{9}$ 以下の整数の重みが定まっていました。

頂点数は $K$ 以上 1000 以下であり、 $1 \le i, j \le K$ に対し、頂点 $i$ と頂点 $j$ の距離は $D_{i, j}$ でした。ただし、頂点 $i$ と頂点 $j$ の距離とは、頂点 $i$ と頂点 $j$ を結ぶ単純パスに含まれる辺の重みの総和のことをいいます。

これらの情報から、ラスク君の持っていた木として考えられるものを一つ出力してください。なお、この問題で与えられる入力に対しては、いずれも条件に整合する木が少なくとも一つ存在することが保証されています。

制約

$2 \le K \le 300$
条件を満たす木は少なくとも 1 つ存在する

考えたこと

テスターだったので、ちゃんと挑んだ。とりあえず、木の直径となる 2 点を考えることにした (必ずしも直径である必要がなかったけど、最初に直径を考えたことで結果的に実装がやや楽になった)。まず $D_{p, q}$ の値が最大となるような 2 頂点 $p, q$ を選んできた ( $l = D_{p, q}$ とする)。

そうすると、残りの各頂点 $v$ に対して、次のことがわかる。

$a = D_{p, v}$ , $b = D_{q, v}$ とする
このとき、頂点は
- 点 $p$ からの距離が $\frac{l + a - b}{2}$ であるような $p-q$ 上の点を経由して
- 直径 ab から距離 $\frac{a + b - l}{2}$ だけ離れた地点に位置する
- このとき、経由した $p-q$ 上の点が存在しないならば新たに追加しておく

これを用いると、点 $p, q$ 以外の各頂点について、「 $p$ からどの程度の距離が離れた地点を経由することになるか」によって分類できることがわかる。そして同一グループについては、その地点を根とする根付き木に関する問題へと帰着できるので、再帰的に解いていけば OK！！

コード

#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int K, N;
vector<vector<long long> > D;
vector<vector<long long> > G;

void solve(const vector<int> &nodes) {
    if (nodes.size() <= 1) return;
    if (nodes.size() == 2) {
        int p = nodes[0], q = nodes[1];
        G[p][q] = D[p][q];
        G[q][p] = D[q][p];
        return;
    }
    
    int p = -1, q = -1;
    long long longest = 0;
    for (int i = 0; i < nodes.size(); ++i) 
        for (int j = 0; j < nodes.size(); ++j) 
            if (chmax(longest, D[nodes[i]][nodes[j]]))
                p = nodes[i], q = nodes[j];

    long long d = D[p][q];
    map<long long, vector<int> > bunrui;
    for (int i = 0; i < (int)nodes.size(); ++i) {
        int v = nodes[i];
        if (v == p || v == q) continue;
        long long a = D[v][p], b = D[v][q];
        long long sum = (d + a + b) / 2;
        long long vdis = sum - d;
        long long pos = a - vdis;
        bunrui[pos].push_back(v);
    }
    
    vector<vector<int> > nnodes;
    long long prev_pos = 0;
    int prev_v = p;
    for (auto it : bunrui) {
        long long cur_pos = it.first;
        int nv = -1;
        for (auto v : it.second) if (D[p][v] == cur_pos) nv = v;
        if (nv == -1) nv = N, it.second.push_back(nv), N++;
        nnodes.push_back(it.second);
        
        G[prev_v][nv] = G[nv][prev_v] = cur_pos - prev_pos;
        for (auto v : it.second) {
            if (v == nv) continue;
            D[v][nv] = D[nv][v] = D[p][v] - cur_pos;
        }
        prev_v = nv;
        prev_pos = cur_pos;
    }
    G[prev_v][q] = G[q][prev_v] = D[p][q] - prev_pos;
    for (auto vs : nnodes) solve(vs);
}

int main() {
    while (cin >> K) {
        D.assign(1000, vector<long long>(1000, 0));
        G.assign(1000, vector<long long>(1000, -1));
        for (int i = 0; i < K; ++i) for (int j = 0; j < K; ++j) cin >> D[i][j];

        vector<int> nodes;
        for (int i = 0; i < K; ++i) nodes.push_back(i);
        N = K;
        solve(nodes);

        cout << N << endl;
        for (int i = 0; i < N; ++i) {
            for (int j = i+1; j < N; ++j) {
                if (G[i][j] > 0)
                    cout << i+1 << " " << j+1 << " " << G[i][j] << " ";
            }
        }
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CPSCO2019 Session4 F - Lost Tree (800 点設定)

問題概要

制約

考えたこと

コード