「キャンディ・アンド・チョコレート」問題
締め切りが 2017/08/10 10:00 AM なので,その 1 分後に投稿されるように予約
設問
n 個のキャンディをグループに分けます。
グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。
例えば、F(8, 3)=5 です。このときの分け方を以下に示します。
なお個々のキャンディを区別せずに扱う点に注意してください。
同様に、F(4, 2)=2,F(20, 6)=90 となることが確かめられます。
次に、n 個のチョコレートをグループに分けます。
グループの数がちょうど k 個となるような分け方の数を G(n, k) と定義します。
例えば、G(9, 4)=6 です。このときの分け方を以下に示します。
同様に、G(4, 2)=2,G(18, 4)=47 となることが確かめられます。
標準入力から、自然数 n と k (1 ≦ k ≦ n ≦ 100)が半角空白区切りで与えられます。
標準出力に F(n, k)+G(n, k) の値を出力するプログラムを書いてください。
例えば入力が「4 2」の場合は、F(4, 2)+G(4, 2) の値である「4」を出力してください。
=======================================================
またも整数分割法である。R でシンプルに書く。
initDiv = function(length, max) {
ary = NULL
repeat {
if (max >= length) {
ary = c(ary, length)
return(ary)
} else {
ary = c(ary, max)
length = length - max
}
}
}
nextDiv = function(ary) {
repeat { # 1でない要素を後ろから探す
sum = 0
for (pos in length(ary):1) {
a = ary[pos]
sum = sum + a
if (a != 1) {
break
}
}
if (ary[1] == 1) { # 全て1
return(FALSE)
}
ary = ary[1:pos]
ary[pos] = ary[pos] - 1
max = ary[pos]
sum = sum - max
pos = pos + 1
repeat {
if (max >= sum) {
ary[pos] = sum
return(ary)
} else {
ary[pos] = max
sum = sum - max
}
pos = pos + 1
}
}
}
F = function(length, max) {
first = TRUE
count = 0
repeat {
if (first) {
d = initDiv(length, max)
first = FALSE
} else {
d = nextDiv(d)
if (length(d) == 1) {
break
}
}
if (d[1] == max) {
count = count+1
} else {
break
}
}
count
}
G = function(length, max) {
first = TRUE
count = 0
repeat {
if (first) {
d = initDiv(length, length)
first = FALSE
} else {
d = nextDiv(d)
if (length(d) == 1) {
break
}
}
if (length(d) == max) {
count = count+1
}
}
count
}
少しやってみると,F(n, k) = G(n, k) であることがわかる。
上のプログラムでは F は G より実行時間が短いので,F の結果を 2 倍すればよいが,それでも n, k によっては実行時間 1 秒という制限にかかる。
よって,n, k の小さい場合についての結果から漸化式を求める。
f = function(n, m) {
a = matrix(0, n, m)
a[,2] = (1:n %/% 2)*2
for (j in 3:m) {
a[j:min(n, 2*j-1), j] = a[j:min(n, 2*j-1)-1, j-1]
for (i in min(n, 2*j):n) {
a[i, j] = a[i-1, j-1] + a[i-j, j]
}
}
a[n, m]
}
爆速である。
> f(20, 7) # 164
[1] 164
> f(35, 7) # 2734
[1] 2734
> f(55, 45) # 84
[1] 84
> f(60, 10) # 125480
[1] 125480
> f(98, 40) # 1428016
[1] 1428016
> f(100, 18) # 22175656
[1] 22175656