Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 319 ConstructBST

|  SRM 319 ConstructBST - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 319 ConstructBST - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6714

二分探索木を作って、各ノードの左の子と右の子の数をカウント。

再帰的に重複組み合わせを計算していく。


import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class ConstructBST {

	Map<Integer, Tree> memo = new HashMap<Integer, Tree>();
	
	class Tree {
		Tree left;
		Tree right;
		int value = 0;
		long s = 0;
		int cl = 0;
		int cr = 0;
		
		public Tree(int v) {
			value = v;
		}
		
		public void putnew(int v) {
			if (v < value) {
				cl++;
				if (left == null) {
					left = new Tree(v);
				} else {
					left.putnew(v);
				}
			} else {
				cr++;
				if (right == null) {
					right = new Tree(v);
				} else {
					right.putnew(v);
				}				
			}
		}
		
		public int countChild() {
			int l = 0, r = 0;
			if (left != null) {
				l = left.countChild();
			}
			if (right != null) {
				r = right.countChild();
			}
			cl = l;
			cr = r;
			return l + r + 1;
		}
		
		public void display() {
			if (left != null) {
				left.display();
			}
			if (right != null) {
				right.display();
			}
		}
	}
	
	public long hp(int n, int m) {
		BigInteger v = BigInteger.valueOf(1);
		for (long l = n + m ; l >= n + 1 ; l--) {
			v = v.multiply(BigInteger.valueOf(l));
		}
		for (long l = m ; l >= 2 ; l--) {
			v = v.divide(BigInteger.valueOf(l));
		}
		return v.longValue();
	}
	
	public long dfs(Tree t) {
		if (t.left == null && t.right == null) {
			return 1;
		}
		if (t.left == null) {
			return dfs(t.right);
		}
		if (t.right == null) {
			return dfs(t.left);
		}
		return dfs(t.right) * dfs(t.left) * hp(t.cl, t.cr);
	}
	
	public void put(int value) {
		boolean isleft = (value % 2 == 0);
		Tree parent = memo.get(value / 2);
		if (parent != null) {
			Tree child = new Tree(value);
			if (isleft) {
				parent.left = child;
			} else {
				parent.right = child;
			}
			memo.put(value, child);
		}
	}

	public long numInputs(int[] tree) {
		java.util.Arrays.sort(tree);
		Tree root = new Tree(1);
		memo.put(1, root);
		for (int i = 1 ; i < tree.length ; i++) {
			put(tree[i]);
		}
		root.countChild();

		return dfs(root);
	}
}