AtCoder ARC 103 E - Tr/ee (青色, 700 点)

取り急ぎ...

問題へのリンク

問題概要

N 頂点からなるツリーがあって、各辺で切ってできる連結成分のサイズとしてありうるものすべて集めたものが指定される。そのようなツリーを 1 つ構築せよ。存在しない場合は -1 とせよ

解法

とりあえず、

• サイズ 1 は絶対存在 (葉があるので)
• サイズ N は絶対存在しない
• サイズ N-1 は絶対存在
• サイズ i が存在するかどうかと、サイズ N-i が存在するかどうかが等しい

が必要条件であることはすぐにわかる。逆にこれを満たすものは比較的容易に作れる。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

using pint = pair<int,int>;

int main() {
    string S; cin >> S;
    if (S[0] == '0' || S.back() == '1') { cout << -1 << endl; return 0; }
    int N = (int)S.size();
    bool ok = true;
    for (int i = 1; i < N; ++i) {
        int j = N - i;
        if (S[i-1] != S[j-1]) ok = false;
    }
    if (!ok) { cout << -1 << endl; return 0; }
    
    vector<pint> res;
    int prev = 1;
    for (int i = 2; i <= N; ++i) {
        if (S[i-1] == '1') {
            for (; prev < i; ++prev) res.push_back(pint(i, prev));
        }
    }
    res.push_back(pint(N, N-1));
    for (auto p : res) cout << p.first << " " << p.second << endl;
}