問題概要

頂点数が $N$ の木であって、各頂点 $1, 2, \dots, N$ から最も遠い頂点への距離がそれぞれ $a_{1}, a_{2}, \dots, a_{N}$ であるような木が存在するかどうかを判定せよ。

制約

$2 \le N \le 100$
$1 \le a_{i} \le N - 1$

考えたこと

面白そう！！！！！！似た見た目の問題としては、次の問題もあった。

drken1215.hatenablog.com

でもちょっと系統は違いそう。とりあえずあーだこーだ考えてみる。「木」についての問題で、距離について考察する問題なので、とりあえず「直径」に着目したくなる。

たとえば、数列が (3, 4, 4, 4, 4, 5, 5, 6, 6, 6) の場合は、最遠が 6 なので直径が 6 だとわかる。するとまずは下図のようになる！さらに言えば、直径上の「最遠距離ラベル」もすべて下図のように確定する！

なぜならば、直径上の頂点に対して、下図の距離ラベルよりも遠い頂点が存在すると仮定すると、「直径よりも長いパス」がとれることになって矛盾するのだ。

よってこの時点で

2 以下は存在したらダメ
3 は存在しないとダメ
4 は 2 個以上ないとダメ
5 は 2 個以上ないとダメ
6 は 2 個以上ないとダメ

ということもわかる。逆に 4, 5, 6 については 2 個より多くあっても、下図のようにいくらでも追加できるので OK。

注意したいこととして、「3」は個数を増やせないことに注意。一般に

直径 $d$ が偶数のとき、距離が $\frac{d}{2}$ の頂点はちょうど 1 個であることが必要
直径 $d$ が奇数のとき、距離が $\frac{d+1}{2}$ の頂点はちょうど 2 個であることが必要

と言える。計算量は $O(N \log N)$ 。

コード

#include <bits/stdc++.h>
using namespace std;

bool solve(vector<int> a) {
    int N = (int)a.size();
    sort(a.begin(), a.end(), greater<int>());
    int vmax = a[0], vmin = a.back();
    if (vmax > N-1) return false;
    if (vmin < (vmax + 1) / 2) return false;
    map<int,int> ma;
    for (auto v : a) ma[v]++;
    
    if (vmax % 2 == 0 && ma[vmin] != 1) return false;
    if (vmax % 2 == 1 && ma[vmin] != 2) return false;
    for (int v = vmin + 1; v <= vmax; ++v) {
        if (ma[v] < 2) return false;
    }
    return true;
}

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    cout << (solve(a) ? "Possible" : "Impossible") << endl;
}

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

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

AtCoder AGC 005 C - Tree Restoring (青色, 700 点)

問題概要

制約

考えたこと

コード