TopCoder SRM 674 Div1 Easy VampireTree

何というひっかけ。
https://community.topcoder.com/stat?c=problem_statement&pm=14000

問題

吸血鬼は人間から新たな吸血鬼を生成できる。
この時、生成した側(主人)とされた側(使用人)は主従関係となる。

全ての吸血鬼は1体の真・吸血鬼から生成されており、この場にいるN体の吸血鬼の主従関係は真・吸血鬼を根とする木構造で表現できる。

ここでi番目の吸血鬼に関するパラメータC[i]が与えられる。
どの吸血鬼が真の吸血鬼か、またどの吸血鬼同士が主従関係にあるかわからないが、以下を満たしていることが分かっている。

• i番の吸血鬼が真の吸血鬼なら、C[i]体の直接的な使用人がいる。
• i番の吸血鬼が真の吸血鬼でないなら、C[i]-1体の直接的な使用人がいる。

この吸血鬼の主従関係において、1つの主従関係の距離を１としたとき、あり得る最遠の吸血鬼の距離を求めよ。

解法

真の吸血鬼以外の(N-1)体は誰かの使用人であるため、C[i]の和は2*N-2であるはずである。
そうでない場合、条件を満たす木構造は存在しない。

あとはC[i]に対して最遠距離が最大となる木構造を作るわけだが、これは単純でC[i]が1より大きい吸血鬼同士が、木構造で幹として直列に並ぶようにすればよい。
他のC[i]が1の吸血鬼は、葉となるようにする。
この時、(C[i]が1でない吸血鬼の数)+1が解となる。

class VampireTree {
	public:
	int N;
	int ret;
	
	
	int maxDistance(vector <int> num) {
		int N=num.size();
		if(accumulate(num.begin(),num.end(),0)!=2*N-2) return -1;
		return 1+(N-count(num.begin(),num.end(),1));
	}
}

まとめ

Nが小さいのでO(2^N)かかるかと思わせておいて、まさかのO(N)。
O(2^N)解法を1時間近くさまよってタイムロスした。