CodeIQ 参加記録

• CodeIQというサイトで問題に挑戦した記録です。
• 気が向いたら不定期に更新します。

第72回「今週のアルゴリズム：左右対称の二分探索木」

• 問題はこちらの「正解者発表」のページから参照下さい。

アルゴリズム
1～nまでのn個の節点を持つ二分探索木においてnが偶数の時は
左右対称のものはできないので、奇数のものについてだけ考える。
二分探索木はある節点の左側は全てその節点より小さい数、
右側はその節点より全て大きい数になるので、左右対称になるのは
1〜nのちょうど真ん中の数を根とした二分木の片側の部分木のパターンの 総数を数えれば良い。

1〜mまでのm個の要素数の二分探索木の総数を考える。
m=1の時、二分探索木は1個
m=2の時、二分探索木は2個
m=3の時、3を根とするm=2のパターン2個とその対称形の
1を根とする2個プラス2を根とする1個の合計5個
m=4の時、4を根とするm=3のパターンとそれの対称形の合計10個
プラス、2を根とする2の左1x右2の2パターン、3を根とする左2x右1の
2パターンの全ての合計14個となる。
ここから漸化式を求めて・・・となるが、
実はこれは カタラン数 として知られており、漸化式は次の通りである。

これを用いてRubyで解答した。(81byte)

gets;m=(n=$_.to_i)%2==0?0:n/2;c=1;(1...m).each{|i|c=2*(2*i+1)*c/(i+2)};p m==0?m:c

正解でした。