久々に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