「ウッド・キーパー」問題解答 ( CodeIQ )

CodeIQというところでプログラミング問題「ウッド・キーパー」に解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 入力される自然数 $n\,(n\le 60)$ に対し、$F(n)$の値を出力する
  • $F(n)$とは $n$本の丸太を次の規則に従って積む積み方の総数である。
    • ある丸太の上に別の丸太を積む場合、同じ高さで隣接する2本の丸太の上に積む必要がある
    • 一番下の段の丸太は、隙間なく繋がっている必要がある

例えば$n=5$の場合、次のような5通りがあるため$F(5)=5$となります。

https://codeiq.jp//sites/default/files/answer_ready/3314/2.png

正しい積み方・誤った積み方としては、問題で次のような例が紹介されていました。

https://codeiq.jp//sites/default/files/answer_ready/3314/1.png

解説

結局のところ、どう漸化式を立てるか、というところなのですが。今回、左端 ( 右端でも良い ) の「崖」に着目しました。崖と言ってるのは、端に何段積んでいるか、その高さを見るものです。

例えば次の図のような状態であれば、右側がどのように積まれていようと、高さ4であるということにします。

f:id:ange1:20170714002409p:plain

ではここで、新たな関数として$g(n,h),\,G(n,h)$を導入します。それは、

  • $g(n,h)=( 崖の高さが丁度hでn個積む場合の数 )$
  • $G(n,h)=( 崖の高さがh以上でn個積む場合の数 )$
    つまり、$G(n,h)=g(n,1)+g(n,2)+g(n,3)+\cdots$

なお、崖の高さ 0 というのはないのですが、便宜上$G(n,0)=G(n,1)$としておきます。するとこのとき、$F(n)=G(n,0)$でもあります。

そうしたら次に、「その高さの崖が作れる条件は?」と考えてみます。例えば、先ほどのように高さ4の崖を作る場合。

f:id:ange1:20170714004052p:plain

問題の制約上、1低い3の崖までなら、高さ4の崖が作れますが、2以上離れてしまうとダメです。ということは、端が高さ$h$の崖になっているということは、その端を除いた積み方は、高さ$h-1$以上ということで、

  • $g(n,h)=G(n-h,h-1)$

ということです。

ここから$g(n,h)$を使わない形に書き換えると、

  • $G(n,h)=g(n,h)+G(n,h+1)=G(n-h,h-1)+G(n,h+1)$
  • $F(n)=G(n,0)=G(n,1)$

これが最終的な漸化式ということになります。

例えば、次の図から数えられるように$F(6)=9$ですが、

f:id:ange1:20170714005912p:plain

次の表のように、$h$が大きい方からどんどん値を伝播させていく ( そして左斜め上の項との合計を計算していく ) ことで、各$G(n,h)$を計算できることが分かります。

f:id:ange1:20170714011224p:plain

ところで、計算は$h$が大きい方から行っているわけですが、じゃあその上限はどこなの? というのは気にする必要があります。

例えば、$n=10$であれば高さの上限は4です。

f:id:ange1:20170714013730p:plain

これは、

  • $n \ge \frac{1}{2}\times h \times(h+1)$

という関係に依ります。裏を返せば、

  • $h \le \frac{1}{2}\times ( \sqrt{8n+1}-1 )$

ということに他なりません。なので、これでめでたく上限も分かりました。

ということで提出コード(Ruby)です。上で示した値の伝播を素直にループで実装したもので計算量$O(n^{1.5})$です。 実を言うと、$n$が小さい所の値はどんどん捨てて行けるのですが、今回それはしていません。

終わりに

割と気付くまでに時間がかかったのですが、整理するとかなり綺麗な漸化式に収まりました。

…でまあ、例によってというかなんというか、これもちゃんとOEISにA005169として収まっているんですよね。いやはや恐ろしい。