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

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

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

面白かった!

問題概要

頂点数が  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 だとわかる。するとまずは下図のようになる!さらに言えば、直径上の「最遠距離ラベル」もすべて下図のように確定する!

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

f:id:drken1215:20201106224124p:plain

よってこの時点で

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

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

f:id:drken1215:20201106224521p:plain

注意したいこととして、「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;
}