はまやんはまやんはまやん

hamayanhamayan's blog

Platform Parkour [Facebook Hacker Cup 2018 Round 1 B]

https://www.facebook.com/hackercup/problem/232395994158286/

N頂点の二分木がある。
各頂点に以下のルールで数を割り当てていく。
全て満たすような割り当てがあれば、それを答えよ。

  • pre-order順で回ったとき、post-order順で回ったときで、それぞれ各頂点の数を配列にすると、等しい配列ができる
  • 各頂点の数は1~Kのどれか
  • 1~Kの数がどれも最低1つは割り当てられる

前提知識

考察過程

1. pre-order, post-orderで回ると、対応する頂点の組が得られる
2. 対応する頂点は同じ数になる必要があるので、同じグループと考えることができる
3. これはUnionFindか
4. 違うグループに属するなら、独立に数の割り当てを考えられる
5. グループの個数が数の割り当ての最大個数となる
6. あとは適当に構築

解法

3段階で解いていく
1. pre-order、post-orderで頂点を巡って、頂点の数を取ってくる順番をそれぞれ得る
2. 1番目通し、2番目通し、…は同じ数になるのでUnionFindでグループ化する
3. それぞれのグループに数を適切に割り当てる
 
1. pre-order、post-orderで頂点を巡って、頂点の数を取ってくる順番をそれぞれ得る
これはdfsで順番を作っていこう。
配列に追加する場所だけ違うので、フラグを使って1つにまとめている(dfs関数)
 
2. 1番目通し、2番目通し、…は同じ数になるのでUnionFindでグループ化する
題名通りUnionFindでグループ化していこう。
 
3. それぞれのグループに数を適切に割り当てる
各グループに1から順番に割り当てていき、Kを割り当てた後は、全てKを割り当てるようにする。
もし、順番に割り当てていき、Kまで行かなかったら、グループ数がK個未満ということなので、
この場合は有効な割り当てが無いとして「-1」を出力する。

int N, K, A[2010], B[2010];
//---------------------------------------------------------------------------------------------------
void dfs(int cu, int isPost, vector<int> &v) {
    if (cu < 0) return;
    if (isPost == 0) v.push_back(cu);
    dfs(A[cu], isPost, v);
    dfs(B[cu], isPost, v);
    if (isPost == 1) v.push_back(cu);
}
//---------------------------------------------------------------------------------------------------
int L[2010];
void solve() {
    cin >> N >> K;
    rep(i, 0, N) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    vector<int> pre, post;
    dfs(0, 0, pre);
    dfs(0, 1, post);

    UnionFind uf(N);
    rep(i, 0, N) uf(pre[i], post[i]);

    int num = 0;
    rep(i, 0, N) if (uf[i] == i) {
        if (num < K) num++;
        L[i] = num;
        
    }
    if (num != K) {
        printf("Impossible\n");
        return;
    }

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", L[uf[i]]);
    }
    printf("\n");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) {
        printf("Case #%d: ", t + 1);
        solve();
        fprintf(stderr, "Finish : %d\n", t+1);
    }
}