TopCoder SRM 674, Division 1, Level 1 : VampireTree

問題文

　https://community.topcoder.com/stat?c=problem_statement&pm=14000&rd=16624

問題概要

　数のリスト $\mathit{ num }$ が与えられる．$| \mathit{ num } | = N$ とする．
　$N$ 頂点の木であって，$i$ 番目の頂点の次数が $\mathit{ num }_i$ であるような木を作るとき，直径（2 点間距離の最大値）の最大値を求めよ．
　木を作れない場合は -1 で示せ．

• $2 \leq | \mathit{ num } | \leq 20$
• $1 \leq \mathit{ num }_i \leq N - 1$

解法

　まずは木を作れるかどうかの判定から考えます．定義に返ってみると，$N$ 頂点の木とは，頂点数が $N$ で辺数が $N - 1$ の連結なグラフです．次数というのは辺 1 本につき $2$ 増えるので，グラフ全体の次数の合計 $\sum_i \mathit{ num }_i$ は $2( N - 1 )$ でなければなりません．これは十分条件にもなっていて，$\sum_i \mathit{ num }_i = 2( N - 1)$ なら必ず木を構成できます．
　このことは，次のように示すことができます．まず，頂点数が最小となる，1 頂点の場合について考えてみると，辺のない 1 頂点のグラフになっていて，これは明らかに木です．
　次に $k$ ($k \geq 2$) 頂点の木に頂点を追加して $k + 1$ 頂点の木を作ることを考えます．このとき，増える次数の内 $1$ は追加される頂点のものです（制約より）．もう $1$ の次数が $k$ 頂点の木の方に増える場合は，元の木と新たな頂点を連結して木を作ることができます．そうではなく，新たな頂点の次数が $2$ の場合は，元の木の葉を新たな頂点で置き換えてから，その頂点に葉をくっつけ直すことで木を得られます（葉の 1 つ内側に新たな頂点を挿入するイメージ）．ということで，数学的帰納法により，どんな頂点数でも次数合計さえ合っていれば木を作れます．

　次に，木を作れるという条件下での最大直径について考えます．試しに以下の図のようなケースを考えてみます．

このとき，赤く着色した頂点と辺を取り外して，上部の横方向に伸びているパスの右端に挿入すると，次の図のような状態になります（取り残される頂点は，赤いのがあったところにくっつける）．

このようにすると，上部の横方向のパスが伸びます．つまり，どこかのパス（この例だと横方向のパス）にくっついている部分から，1 頂点だけ残してパスに挿入することで，着目しているパスを伸ばすことができます．パスにどのようなものがくっついているとこの操作が可能かを考えてみると，次数 2 以上の頂点がくっついていれば，そこから先を付け替える操作ができることが分かります．つまり，この操作を繰り返し適用することで，次数 2 以上の頂点を全て単一のパスに含めることができて，このときに最大の直径を達成できます．従って，最大直径は，次数 2 以上の頂点の数 + 1 となります．

コード

#define ALL( c ) begin( c ), end( c )

#define SZ( v ) ( (int)( v ).size() )

class VampireTree
{
public:
	int maxDistance( vector <int> num )
	{
		const int N = SZ( num );

		if ( accumulate( ALL( num ), 0 ) != ( N - 1 ) * 2 )
		{
			return -1;
		}

		return count_if( ALL( num ), bind( greater< int >(), _1, 1 ) ) + 1;
	}
};