「今週のお題：バランスの良いカーテンフック」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- カーテンレール上のランナーと、そこに吊るすフックの個数がカンマ区切りで入力される
- フックのないランナーが連続しないような吊るし方 ( フックは全部使う ) が何通りあるかを出力する
- ただし、両端のランナーには必ずフックを吊るすものとする
詳細は次のCodeIQマガジンの記事をご覧ください。 codeiq.jp
解説
ランナー・フックの数をそれぞれr,hとした場合、フック同士の隙間 $h-1$箇所に、 フック無しのランナー$r-h$個を割り当てる ( 1箇所につき0個または1個 ) ということになるため、 組み合わせ ${}_{h-1}C_{r-h}$ により計算できます。
ということで、Rubyによる実装(63文字)は次のようになります。
r,h=eval ?[+gets+?]
a=1
1.upto(r-h){|i|a=a*(h-=1)/i}
p r<h ?0:a
…最初、妥当な配置がない ( rの方が小さい ) ケースのケアを忘れていて、WAを食らったのは内緒です。
終わりに
簡単な問題はWA食らわないよう、一発で決めたいところですね。
