TopCoder SRM 585 Div1 Easy TrafficCongestion

SRM585に参加。Easyはさっくり解けたけど、Mediumが最後詰め切れず。
本番ちょっとサーバが混んでたのか、最初図が表示されず、ログインし直しで１分損したのが残念。
レートは若干上がったからまぁいいか。
http://community.topcoder.com/stat?c=problem_statement&pm=11361

問題

数Hに対して、高さHの二分木を考える。
この二分木上を複数の車が走る。各車は互いに同じ点を２度通れない。

Hが与えられるとき、全部の点を辿るのに必要な車の数を答えよ。

解法

色んな考え方があると思うけど、自分のケースを書いておく。
２分木について、一番左下の点から、頂点をとおって右下にたどる車を１台通す。
すると、残った点は高さ(H-2)の木が２つ、(H-3)の木が２つ、…、0の木が２つになる。

後は漸化式を辿るだけ。

ll res[1000001];
ll mo=1000000007;

class TrafficCongestion {
	public:
	int theMinCars(int treeHeight) {
		int i;
		res[0]=1;
		res[1]=1;
		res[2]=3;
		ll tot=res[0]+res[1];
		for(i=3;i<=1000000;i++) {
			res[i]=(1+tot*2)%mo;
			tot+=res[i-1];
		}
		
		return (int)res[treeHeight];
	}
};

まとめ

ほかの人の解法を見ると、同じ考えの人もいたし、だいぶ異なった解法の人もいた。
他の人がどういう考えで解法に至ったか気になるな。