kmjp's blog

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

TopCoder SRM 666 Div1 Easy WalkOverATree

久々にEasy/Medium両方早解き出来て良い出来でした。
朝回とはいえ10位は自己ベスト。
http://community.topcoder.com/stat?c=problem_statement&pm=13955

問題

N頂点の木が与えられる。
この木で0番の点からスタートし、隣接点を辿る、という処理を最大L回行う。
途中同じ点を複数回たどっても良い。
最大で何個の頂点を辿ることができるか。

解法

0番の頂点を深さ0とし、各頂点iの深さをD[i]とする。

最後に停止する点をiとする。
D[i]≦Lならiに到達可能で、0番からi番に最短で移動すると(D[i]-1)回の移動で(D[i]+1)頂点を辿ることができる。
その場合、0→i番の最短経路の点を経由しようとする場合、2回余分に移動することで1つ経由する頂点を増やすことができる。
よってその場合最大で経由できる頂点は(D[i]+1)+max*1/2, N-(D[i]+1))となる。

上記式を各iに対し求めても良いし、上記式はD[i]が大きいほど大きくなるので、最大のD[i]について1回計算しても良い。
いずれにしてもO(N)で終わる。

class WalkOverATree {
	public:
	int D[51];
	
	int ma=1;
	int maxNodesVisited(vector <int> parent, int L) {
		int N=parent.size()+1;
		int i,ma=1;
		
		D[0]=0;
		
		FOR(i,N) {
			if(i) D[i]=D[parent[i-1]]+1;
			if(D[i]>L) continue;
			int ret=D[i]+1;
			ret=ret+min((L-D[i])/2,N-ret);
			ma=max(ret,ma);
		}
		return ma;
	}
}

まとめ

割とすんなり思いついて良かった。

*1:L-(D[i]-1