「 今週のお題:長男はいつも弟のことを考える?」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

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

  • 長方形のマス目状になっているチョコレートを兄弟で分割するとき、次の条件を満たす分け方は何通りあるかを出力する
    • マス目に沿って縦もしくは横に分割する
    • 1人に分けるたびに1度分割し、左上の部分をその人に割り当てる
    • 全員に1マス分以上のチョコレートがいきわたるようにする
    • なお、サイズが同じであっても、分割する位置や順序が異なる場合は、異なる分け方とみなす
  • 縦のサイズ、横のサイズ、分ける人数がカンマ区切り1行で入力される

問題に挙げられていた 3×4のマス目、3人で分割の例だと、次の画像のように16通りとなります。

https://codeiq.jp/sites/default/files/answer_ready/2892/q42_2.png

解説

「割る」という行為は、縦もしくは横の線を引くことにほかならず、そうすると n 人に対して縦に x 本、横に y 本引くとすると ( この時$x+y=n-1$ )、それぞれ線を引く位置の選び方は ${}_{w-1}C_x,\,\,{}_{h-1}C_y$通りとなります ( w,hはそれぞれ横・縦のサイズ )。

後は、縦・横の線を引く順序があるため、 $$ \sum {}_{w-1}C_x\times{}_{h-1}C_y\times{}_{n-1}C_x $$ を計算することで答えが出ます。

この計算に基づき次のRubyのコードを提出しました。

c=->m,k{(1..[m,m-k].min).reduce(1){|s,i|s*(m+1-i)/i}}
n,w,h=eval ?[+gets+?]
puts ([0,n-h].max..[w,n].min-1).reduce(0){|s,i|s+c[w-1,i]*c[h-1,n-i-1]*c[n-1,i]}

終わりに

再帰等でも解けるような気がしたのですが、Σで書ける式ならそのまま計算した方が良いかな、ということでこういう解き方にしました。やっぱり数式で扱える方がやりやすいですね。