「キャンディ・アンド・チョコレート」問題

「キャンディ・アンド・チョコレート」問題

締め切りが 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