ibeckuuの日記

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第102回「長男はいつも弟のことを考える？」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

マス目状のチョコレートを縦か横に一直線に分割する事を考える。
(マスの途中では割れない)
標準入力から縦・横・人数が与えられ、全員が食べられる様に分割するパターンが何通りかを解答する。
分割の方法・・・縦か横に一直線に切り取り、左か上のものを取り除き、残ったものを同じ方法でカットを繰り返す。
縦・横の最大はそれぞれ20、人数の最大は10

方針

3通りのアルゴリズムで解答する。

メモ化再帰
動的計画法
組み合わせ論で計算

アルゴリズム

1. メモ化再帰

縦h、横wのマスをn人で分ける場合の数を考える。

f:id:ibeckuu:20160727223647j:plain

n人で分けるためにはn-1回分割する事になる。

1回目からn-1回目までのカットにおいて、前回のカット位置の縦・横それぞれの次の位置からh-1、w-1の位置まで全てのカット位置を試し、n-1回カットしたパターンを再帰関数で数える。
高速化の為、メモ化を用いる。

実装(Ruby)

2. 動的計画法

縦h、横wのマスを縦i、横jのカット位置でk回目に切り取る場合の数は下記の漸化式で表す事ができる。

${f(1,i,j)=1}$ ( ${1 \leq i \leq h-1}$ , ${j=0}$ ) または ( ${i=0}$ , ${1 \leq j \leq w-1}$ )
${f(k,i,j)= }$ ${\sum _{p=0}^{i-1} f(k-1,p,j) + }$ ${\sum_{q=0}^{j-1} f(k-1,i,q)}$

漸化式の説明

k回目に(i,j)の位置をカットする場合の数は、

f:id:ibeckuu:20160727224653j:plain

k-1回目に(0,j)の位置でカットされたものから(i-1,j)の位置でカットされたものの全ての場合の数を加算したものと

f:id:ibeckuu:20160727224604j:plain

f:id:ibeckuu:20160727224629j:plain

k-1回目に(i,0)の位置でカットされたものから(i,j-1)の位置でカットされたものの全ての場合の数を加算したものである。

f:id:ibeckuu:20160727224723j:plain

f:id:ibeckuu:20160727224741j:plain

実装(JavaScript / SpiderMonkey)

3. 組み合わせ論による

縦h、横wのマスを縦か横かにn-1回カットする場合の数は、
h-1個の区切り位置からi個を選び、

f:id:ibeckuu:20160727224845j:plain

w-1個の区切り位置からn-1-i個を選ぶ組み合わせに

f:id:ibeckuu:20160727224907j:plain

縦・横の同じものを含む順列を掛けたもの。
これをiについて0からh-1かw-1の小さい方までの総和で計算できる。

式は下記の通り。

${s=min(h,w),b=max(h,w),r=min(s,n)}$ とする
${f(n)=}$ ${\sum_{i=0}^{r-1}}$ ${\verb#{#}$ ${ _{s-1}C_{i} }$ ${ \times _{b-1}C_{n-1-i} \times \frac{ (n-1)!} { {i!} \times {(n-1-i)!} }}$ ${ \verb#}# }$

実装(JavaScript / SpiderMonkey)

では、

Sponsored Link