2019-12-15

AtCoder ARC 103 F - Distance Sums (赤色, 900 点)

AtCoder AtCoder900点構築 Greedy Greedy:端から順に決まっていく決めてから整合性を確認する最大値や最小値に着目する葉から考える木構築:木復元探索順序を工夫して解く赤色diff ARC-F 木の問題に対してパスの場合から考える

900 点なので備忘録程度に...
久しぶりに競プロでめちゃくちゃ楽しかった！！！
2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。

問題へのリンク

問題概要

以下の条件を満たす $N$ 頂点の木を復元せよ。ただし、存在しない場合には -1 と出力せよ。

各頂点 $i$ について、その頂点から他の頂点への距離の総和が $D_i$ である

制約

$2 \le N \le 10^{5}$

考えたこと

こういう構築系では、きっと

なにか上手に上手い視点で見ると、木の形があれよあれよと一意に決まるので、最後に整合性を check する

という風になるんだろうな...という想定があった。ましてや $N \le 10^{5}$ なので... $N \le 10^{5}$ とかいう設定で、探索予想はなかろう。。。

で、どこから着目したらいいんだろう...と悩んでいたところに少し思ったのは

D の値が最小の頂点
D の値が最大の頂点

がなんとなくポイントになりそうな気がした。ひとまず、特殊なグラフで観察してみる。

結論からいうと、D の値が大きい順に考えると一意にドンドン決まっていく。最初は D の値が小さい順に考えようとして上手くいかなかった。この辺は試行錯誤するよりないとは思うけど、D が大きい順に考えることにこだわった時間が長かったので、そこの方針の切り捨てがもう少し早ければもっと早く解けたかもしれない。

パスグラフの場合の観察

$N = 7$ とかだと、21, 16, 13, 12, 13, 16, 21 とかになる。
他の例も見て思ったのは、一般に

木上の任意のパスについて、その D 値は凹関数になっている (その証明はそんなに難しくはない)
最大の D は葉になる
両端を根とする部分木がバランスするような辺において、その両端の D 値は近い

とかその辺りのことを思った。

根付き木として考えてみる

ひとまず、以下のことを示した

$D$ の値が最小の頂点 $r$ を根とした根付き木にすると、どの葉に対しても、根から葉へいたる経路中の $D$ の値は単調増加である

$r$ の子頂点の 1 つを $c$ としたとき、木を辺 ( $r, c$ ) で分断してできる両側の部分木を考えたとき、 $r$ が最小であることから、 $r$ 側の部分木の方がサイズが大きく、 $c$ 側の部分木の方がサイズが小さい。

よって、 $c$ 側の部分木のサイズは $N$ / 2 以下である。さらに、 $c$ の子頂点 $c'$ を考えても、その子頂点を根とする部分木のサイズは $N$ / 2 以下なので、 $D_{c'}$ は $D_{c}$ より小さい。以下同様のことがいえる。

辺の両端の部分木のサイズと、辺の両端の D の値の差について

以上の証明で、暗黙に使っている事実がある。それは、

辺 $(u, v)$ について、この辺で木を分断したときの、 $u$ 側と $v$ 側の部分木のサイズを $S_u, S_v$ とする
このとき、 $D_u + S_u = D_v + S_v$ が成立する

再び根付き木に

ここで再び、 $D$ の値が最小の頂点を根とする根付き木を考える。根付き木には「親がただ一つ存在する」という著しい特徴があるので、各頂点につき、親を求めれば根付き木が決まるのだ！！！！！そして、親の $D$ 値は子の $D$ 値よりも小さい。

まず $D$ の値が最大の頂点 $v$ は葉といえる
しかも上の性質から、親 $p$ の $D$ 値は $D_{v} + (N - 2)$ であることもいえてしまう
一般に $D$ が大きい順に決めて行ったとき、今考えている頂点を $v$ とすると、 $v$ を根とする部分木のサイズは確定している ( $v$ よりも $D$ 値の小さい頂点が子孫になることはないため)
よって、 $v$ の親の $D$ 値も一意に決まってしまう！！！

上記のことを繰り返すと、根付き木の形としてありうるものが一意に決まってしまう！！！！！！！！！！！！！

最後にそれが整合するかを check した。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using Tree = vector<vector<int>>;

int N;
vector<long long> D;
map<long long, int> dtoi;
vector<int> subtree_size;

long long rec(const Tree &G, int v) {
    long long res = 0;
    for (auto c : G[v]) {
        res += rec(G, c) + subtree_size[c];
    }
    return res;
}

void solve() {
    subtree_size.assign(N, 1);
    vector<int> par(N, -1);
    Tree G(N);

    // greedy from leaves
    sort(D.begin(), D.end(), greater<long long>());
    for (int i = 0; i < N-1; ++i) {
        int id = dtoi[D[i]];
        int s = subtree_size[id];
        long long l = N - s * 2;
        long long nextD = D[i] - l;
        if (!dtoi.count(nextD)) {
            cout << -1 << endl;
            return;
        }
        int nid = dtoi[nextD];
        par[id] = nid;
        subtree_size[nid] += subtree_size[id];
        G[nid].push_back(id);
    }

    // final check
    long long DD = rec(G, dtoi[D.back()]);
    if (DD != D.back()) {
        cout << -1 << endl;
        return;
    }

    // output
    for (int i = 0; i < N; ++i) {
        if (par[i] == -1) continue;
        cout << i+1 << " " << par[i]+1 << endl;
    }
}

int main() {
    cin >> N;
    D.resize(N);
    for (int i = 0; i < N; ++i) cin >> D[i], dtoi[D[i]] = i;
    solve();
}