「ウッド・キーパー」問題解答 ( CodeIQ )
CodeIQというところでプログラミング問題「ウッド・キーパー」に解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力される自然数 $n\,(n\le 60)$ に対し、$F(n)$の値を出力する
- $F(n)$とは $n$本の丸太を次の規則に従って積む積み方の総数である。
- ある丸太の上に別の丸太を積む場合、同じ高さで隣接する2本の丸太の上に積む必要がある
- 一番下の段の丸太は、隙間なく繋がっている必要がある
例えば$n=5$の場合、次のような5通りがあるため$F(5)=5$となります。
正しい積み方・誤った積み方としては、問題で次のような例が紹介されていました。
解説
結局のところ、どう漸化式を立てるか、というところなのですが。今回、左端 ( 右端でも良い ) の「崖」に着目しました。崖と言ってるのは、端に何段積んでいるか、その高さを見るものです。
例えば次の図のような状態であれば、右側がどのように積まれていようと、高さ4であるということにします。
ではここで、新たな関数として$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の崖を作る場合。
問題の制約上、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$ですが、
次の表のように、$h$が大きい方からどんどん値を伝播させていく ( そして左斜め上の項との合計を計算していく ) ことで、各$G(n,h)$を計算できることが分かります。
ところで、計算は$h$が大きい方から行っているわけですが、じゃあその上限はどこなの? というのは気にする必要があります。
例えば、$n=10$であれば高さの上限は4です。
これは、
- $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として収まっているんですよね。いやはや恐ろしい。