kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2015 Round1C Medium UnrelatedPaths

なんだこの問題…。
http://community.topcoder.com/stat?c=problem_statement&pm=13746

問題

N頂点の根付き木を考える。

ここからいくつかのパスを取りたい。
その際、あるパス上の頂点の祖先が、他のパス上の頂点となる、ということが無いようにしたい。
選べる最大パス数はいくつか。

解法

問題をよく読むと、パスの長さは0であっても良いことがわかる。
よって葉の頂点数を答えればよい。

class UnrelatedPaths {
	public:
	int maxUnrelatedPaths(vector <int> parent) {
		int i,N=parent.size()+1;
		int hc[52]={};
		
		for(i=N-1;i>=1;i--) hc[parent[i-1]] = 1;
		int ret=0;
		FOR(i,N) ret += 1-hc[i];
		return ret;
	}
}

まとめ

せめてパス長が1以上とかの縛りを付ければよかったのにな。
…自分は最初暗黙にその縛りを仮定して解こうとしてしまった。