TopCoder SRM 585, Division 1, Level 1 : TrafficCongestion

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11361&rd=15697

概要

完全二分木の高さが与えられる。
全ての頂点をちょうど一度ずつ被覆するパス集合の最小サイズを求めよ。

解法

高さ k + 1 の木に於ける根ノードの子は高さ k の完全二分木です。
高さ k に於ける結果が分かっているとき、高さ k + 1 の結果がどうなるかを考えます。
高さ k + 1 に於ける結果は、高さ k に於ける結果に於いて根を端点とするパスが存在するかどうかによって分けられます。
そのようなパスが存在するかどうかは奇偶によって場合分けされ、k が奇数であれば存在します。
存在する場合はそれらのパスを連結し、そうでない場合は根からどちらかの子の根へ繋げます。
従って、高さ k での結果を dp[k] とすると、

• dp[k] = dp[ k - 1 ] * 2 - 1 ( k mod 2 == 1 )
• dp[k] = dp[ k - 1 ] * 2 + 1 ( それ以外 )

また、dp[0] = dp[1] = 1 です。
この表を順に埋めることで答えが得られます。

コード

typedef long long LL;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int MOD = 1000000007;

class TrafficCongestion
{
public:
	int theMinCars( int treeHeight )
	{
		vector<LL> dp( 1000001, 0 );
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 3;
		REP( i, 3, treeHeight + 1 )
		{
			if ( i % 2 )
			{
				( dp[i] += ( dp[ i - 1 ] * 2 - 1 ) % MOD ) %= MOD;
			}
			else
			{
				( dp[i] += ( dp[ i - 1 ] * 2 + 1 ) % MOD ) %= MOD;
			}
		}
		return dp[ treeHeight ];
	}
};