Atcoder AGC #005 C. Tree Restoring

Atcoder AGC #005 C. Tree Restoring

C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder

頂点iからみて最も遠い点までの距離がa[i]として与えられるので、そのような木が構成可能かを答える問題。とりあえずa[i]の最小値が、3個以上ある場合は構成不可能であることが簡単に示せる。そこで、その最小値minを根として根付き木を考えた。まず、minが1個のときは、minから少なくとも2つの辺が出ていて、（minがそれ唯一であることを考慮すると）どちらの最大の深さもminであるような木でなければならないことに気づく。そのような木を構成するためにはまず、m< a[i] <= 2mであるようなa[i]がそれぞれ最低2個あるkとが必要である。そしてa[i] > mであるようなa[i]がないことも確認すれば、これで判定が終わる。なぜなら、他のすべてのm < a[i] <= 2mに関して、それがa[i] = m + kを満たすとすると、左右どちらかの深さkの位置に新しい子としてくっつけてやれば、他のどの頂点の値も変えることなく、a[i] = m + kとなるように木を拡大できるからである。一方、minが2個あるときは、まずminを根にし、その隣にもminをつけ（これを仮に左の子につけるとする）、左の深さをmin、右の深さをmin - 1にすることで、上と同様のことができる。このとき、条件がm < a[i] < 2mに変わることに気をつけること。

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

int print(bool ok) {
        if (ok) cout << "Possible" << endl;
        else cout << "Impossible" << endl;
        return 0;
}

int main() {
        int n, a;
        cin >> n;
        int mi = 110;
        int cnt[200] = { 0 };
        for (int i = 0; i < n; i ++) { 
                cin >> a;
                cnt[a] ++;
                mi = min(mi, a);
        }
        if (cnt[mi] > 2) return print(0);
        for (int i = mi + 1; i < 2 * mi + (cnt[mi] == 1 ? 1 : 0); i ++) if (cnt[i] < 2) return print(0);
        for (int i = 2 * mi + (cnt[mi] == 1 ? 1 : 0); i < 200; i ++) if (cnt[i] > 0) return print(0);
        return print(1);
}

700点前後の問題が自力で解けるようになってきた感じが嬉しい。