「今週のお題：左右対称の二分木」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
しばらく書けずにいたら溜まってしまったので、年明け前にはなんとか…。
codeiq.jp
問題
表題の通り、二分木の中で左右対称なものの個数を数えるものです。詳細はこちらを。
入力 n に対して、木のノードには、(半)順序関係を保って 1～n の数字をあてはめるのですが、あくまで「形」を数えるだけなので気にする必要はありません。なぜならば、どんな形であれ、問題にあるような順序関係を満たす数字のあてはめかたがあるからです。
解説
数式の整理
まず、左右対称なのですから n が奇数でなければ答えは 0 です。
そして、ルート ( てっぺんの ) ノードを除いた片側については特に制約のないタダの二分木です。( もう片側はもちろん、左右反転させた形として一意に決まります )。
ということは、解を$f(n)$、制約のないサイズmの二分木の個数を$g(m)$とすると、次のような関係があります。
- $ f(n)=\left\{ \begin{array} 2g(\frac{n-1}{2}) & ( nが奇数 ) \\ 0 & ( nが偶数 ) \end{array}\right. $
さて、$g(m)$に関しては、ルートの左右、計n-1ノードをどう配置するか、ですから、次の漸化式が成立します。
- $ g(m)=\sum_{k=0}^{m -1}g(k)g(m -1-k) $
なお、初期値としては$g(0)=1$が妥当です。これで数式の整理ができました。
式の簡略化
しかしながら、先ほどの式ではnの偶奇による場合分けがあって ( 文字数的に ) 面倒です。
そこで$g(m)$の計算をちょっと変えてみます。
これは$g(5)$を計算する例です。線でつながれている項同士の積を計算し、合計しています。しかし、各項の間に0を挟んでも同じことですね。
こうすると何が嬉しいか。次に同じ漸化式で計算を行った場合、全て 0 の掛け算になりますから、合計が 0 ということで、「0が1つおきに現れる」という性質を持続させられるところです。
…これはもはや、求めるべき$f(n)$そのものに他なりません。そこで、f,g の使い分けや場合分けをなくして、次のようにまとめることができます。
- $f(0)=0,\ f(1)=1$
- $f(n)=\sum_{k=0}^{n-1}f(k)f(n-1-k)\ \ (n\geq 2)$
実装
ということで前置きが長くなりましたが、以下が提出版 ( 関数名は変えてますが ) の実装です。
素直に漸化式をメモ化再帰として書いただけですね。
もっと短い書き方はありそうですが、まあ単純な形にはなっていますから、深く追求しませんでした。
m=[0,1]
f=->n{m[n]||=(0..n-=1).inject(0){|s,i|s+g[i]*g[n-i]}}
p f[eval *$<]
終わりに
さて年内に終わるかな…
