読者です 読者をやめる 読者になる 読者になる

ACM-ICPC World Finals 2016 C解法

C: Ceiling Function

問題

n個のk頂点-二分探索木が与えられる。
二分探索木は挿入する値とその順番によって与えられる(回転などはしない)。
何種類の形があるか数えよ。

制約

1 <= n <= 50
1 <= k <= 20
各木の要素は互いに異なる値である。

解法

根付き木の同型性判定問題。
サイズが小さいので、木を陽に持ち全てのペアに対して、同時に探索を行うことで判定するのが簡単。

より大きなサイズの問題について考えると、木の同型性判定はハッシュを用いる方法がある。

コード

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }


struct Tree {
    int v;
    Tree *l, *r;
    Tree(int v_=0) {
	v = v_;
	l = r = NULL;
    }
};
Tree * insert(Tree *x, int v) {
    if (!x) return new Tree(v);
    if (v < x->v) {
	x->l = insert(x->l, v);
    } else {
	x->r = insert(x->r, v);
    }
    return x;
}

bool same(Tree *x, Tree *y) {
    if (!x && !y) return true;
    if (!x || !y) return false;
    return same(x->l, y->l) && same(x->r, y->r);
}

int N, K;
Tree *tree[55];
bool use[55];

int main() {

    scanf("%d%d", &N, &K);
    REP (i, N) {
	REP (j, K) {
	    int v;
	    scanf("%d", &v);
	    tree[i] = insert(tree[i], v);
	}
    }


    int ans = 0;
    REP (i, N) {
	if (use[i]) continue;

	ans++;
	for (int j=i+1; j<N; j++) {
	    if (same(tree[i], tree[j])) {
		use[j] = true;
	    }
	}
    }

    printf("%d\n", ans);

    return 0;
}