Hashing Trees [Codeforces Round #453 A]

http://codeforces.com/contest/901/problem/A

高さHの木を考える。
高さiの頂点数がa[i]である。

これを満たす根付き木がただ1つに定まるなら「perfect」を出力する。
もし、複数個あるなら「ambiguous」と出力し、その中から2例出力せよ。

解法

http://codeforces.com/contest/901/submission/33470286

まず、ただ1つに定まる条件を考えてみよう。
これは色々実験してみると「隣り合う2つの高さの頂点数でどちらも2以上となる組が存在しない」と分かる。
なので、これを見てみて、存在すれば「ambiguous」として2通りの木を構築しよう。
　
木の構築では「集める」と「散らす」で作ろう。
「集める」では、なるべく1つの頂点に子をくっつけるようにする。
「散らす」では、なくべく多くの頂点に子をくっつけるようにする。

int H, A[101010];
int N;
//---------------------------------------------------------------------------------------------------
void ambiguous() {
    N = 0;
    rep(i, 0, H + 1) N += A[i];
    printf("ambiguous\n");

    vector<int> v, ans;

    // gathar
    v.push_back(0);
    int id = 1;
    rep(i, 0, H + 1) {
        vector<int> w;
        rep(j, 0, A[i]) {
            ans.push_back(v[0]);
            w.push_back(id);
            id++;
        }
        swap(w, v);
    }
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");

    // scatter
    v.clear(); ans.clear();
    v.push_back(0);
    id = 1;
    rep(i, 0, H + 1) {
        vector<int> w;
        rep(j, 0, A[i]) {
            ans.push_back(v[j % v.size()]);
            w.push_back(id);
            id++;
        }
        swap(w, v);
    }
    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");

}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H;
    rep(i, 0, H + 1) cin >> A[i];

    rep(i, 0, H) if (1 < A[i] and 1 < A[i + 1]) {
        ambiguous();
        return;
    }

    printf("perfect\n");
}