ブログを書くネタもあまりないので、プログラミングつながりということで
自分のまとめも兼ねてTopCoderのソースコードも公開して行きたいと思います。
#本当は、ちゃんとしたアーカイブしたいけど
ちなみに、ソースコードはGitHubのURLを貼るだけです。
#リクエストがあれば何かするかも
TopCoder自体は2年くらい前からやってましたが、スコアは低いです。頑張ります。
というわけで早速。
SRM 585 Div 2
Easy
LISNumberDivTwo
http://community.topcoder.com/stat?c=problem_statement&pm=12446
ソース:
https://raw.github.com/yuki2006/topcoder/master/src/LISNumberDivTwo.java
Medium
TrafficCongestionDivTwo
http://community.topcoder.com/stat?c=problem_statement&pm=12697
ソース:
https://github.com/yuki2006/topcoder/blob/master/src/TrafficCongestionDivTwo.java
特に、TrafficCongestionDivTwo の方は、興味深かったので説明書きます。
本番で書いたコードはなんとなく見つけた法則でのメモ化再起なんですが
SRM終了後に
他の人のエレガントなアルゴリズムを考えていた時に、見つけたアルゴリズムです。
（System Testには通りましたが、理論的に説明できません。。）
しかも、「倍数の証明 ジェネレータ」
http://tma.main.jp/baisuu/
というさらに興味深いサービス見つけたので、更にはかどりました。
高さh+1の完全二分木のノード数 は 2^h -1 です。
ここで問題でいう１つのパスを 葉のノード →その上のノード →右下の葉のノード
を順番にやっていくと最小のパス集合数になるのではと思いました。
（理論的に証明できません。。
ここで、 hが偶数のとき, ノード数は3の倍数になることの証明はこちら
2^(2n) -1 = 4^n -1 が 3の倍数であることの証明
http://tma.main.jp/baisuu/baisuu.php?eq=4%5En-1&num=3
また hが奇数の時、ノード数は3で割ったら1余る証明はこちら （少し変形してます
2^(2n+1) -1 -1 が 3の倍数であることの証明
http://tma.main.jp/baisuu/baisuu.php?eq=2%5E%282*n%2B1%29-2+&num=3
つまり、
hが偶数の時は、先ほどの長さ3のパスの組み合わせで構成可能
hが奇数の時は、長さ3のパスの組み合わせで構成すると根のノードだけ残る（あまり１）
つまり、
(2^h -1)/3 の切り上げの値が 最小のパス集合の数と等しくなるではないかと思いました。
2^h-1 % 3のあまりの最大値は１なので
切り上げを表現するためにテクニカルな方法を用いて+2にしました
つまりreturn文はなんと一行で表現出来ました。
return ((long) Math.pow(2, treeHeight + 1) - 1 + 2) / 3;
ツッコミお待ちしております。
