「 今週のお題:長男はいつも弟のことを考える?」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 長方形のマス目状になっているチョコレートを兄弟で分割するとき、次の条件を満たす分け方は何通りあるかを出力する
- マス目に沿って縦もしくは横に分割する
- 1人に分けるたびに1度分割し、左上の部分をその人に割り当てる
- 全員に1マス分以上のチョコレートがいきわたるようにする
- なお、サイズが同じであっても、分割する位置や順序が異なる場合は、異なる分け方とみなす
- 縦のサイズ、横のサイズ、分ける人数がカンマ区切り1行で入力される
問題に挙げられていた 3×4のマス目、3人で分割の例だと、次の画像のように16通りとなります。
解説
「割る」という行為は、縦もしくは横の線を引くことにほかならず、そうすると 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]}
終わりに
再帰等でも解けるような気がしたのですが、Σで書ける式ならそのまま計算した方が良いかな、ということでこういう解き方にしました。やっぱり数式で扱える方がやりやすいですね。