読者です 読者をやめる 読者になる 読者になる

「今週のお題:バランスの良いカーテンフック」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

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

  • カーテンレール上のランナーと、そこに吊るすフックの個数がカンマ区切りで入力される
  • フックのないランナーが連続しないような吊るし方 ( フックは全部使う ) が何通りあるかを出力する
  • ただし、両端のランナーには必ずフックを吊るすものとする

詳細は次の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食らわないよう、一発で決めたいところですね。