TopCoder SRM 591 Div1 Easy TheTree

SRM591に参加。Mediumが解けなかったけど、Easyが早めに解けてChallengeを１つ決めたこともありそこそこの順位に終わった。
時間帯的に参加者が少ないのでレート増加量は微量だけど、最高値を更新できたのでいいか。
http://community.topcoder.com/stat?c=problem_statement&pm=12746

問題

ある点をrootとする木構造のグラフ構造を考える。
rootからの距離がiの点がC[i]個あるとする。
数列Cに対し、ありうる２点間の距離の最大値を求めよ。

解法

２点間の距離を考えるので、距離iの点は高々２個しか通らないので、C[i]が３個以上なものは無視して、１～２個だけ考えればよい。

距離の最大値がNとして、一番左下の点から初めてi=0～Nの点で折り返す場合の最長距離を求めればよい。

class TheTree {
	public:
	int N;
	vector<int> V;
	int mat(int id) {
		int i;
		int ret=N-id;
		for(;id<N;id++) {
			if(V[id]==1) break;
			ret++;
		}
		return ret;
	}
	
	int maximumDiameter(vector <int> cnt) {
		int i;
		int ma=0;
		N=cnt.size();
		FOR(i,N) if(cnt[i]>2) cnt[i]=2;
		V=cnt;
		
		ma=N;
		FOR(i,N) {
			if(cnt[i]==1) break;
			ma++;
		}
		
		FOR(i,N) ma=max(ma,mat(i));
		return ma;
	}
};

まとめ

これは本番すぐに回答が思いついてよかった。
WFで解いた人もいたみたいね。