CodeIQ：グループで乗るリフト

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「グループで乗るリフト」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
m 人のグループがスキー場でリフトやゴンドラに乗ろうとしています。
このスキー場には n 人乗りのリフトやゴンドラがあります。
グループでまとまって移動するため、連続したリフトやゴンドラに乗ることにします。

グループのメンバーは区別せず、各リフトやゴンドラに乗る人数だけを考えるとき、1回の移動における乗り方が何通りあるかを求めてください。

ただし、誰も乗らないリフトやゴンドラはないものとします。
また、m, n ともに 32以下の正の整数とします。

例えば、m = 5, n = 3 のとき、以下の13パターンがあります。
パターン 1台目 2台目 3台目 4台目 5台目
(1) 1人 1人 1人 1人 1人
(2) 1人 1人 1人 2人 -
(3) 1人 1人 2人 1人 -
(4) 1人 2人 1人 1人 -
(5) 2人 1人 1人 1人 -
(6) 1人 1人 3人 - -
(7) 1人 3人 1人 - -
(8) 3人 1人 1人 - -
(9) 1人 2人 2人 - -
(10) 2人 1人 2人 - -
(11) 2人 2人 1人 - -
(12) 2人 3人 - - -
(13) 3人 2人 - - -

【入出力サンプル】
標準入力
5 3

標準出力
13

私のプログラム

Rubyで解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/ruby
 
$Memo = {1=>1}
 
def solve(m, n)
    if m == 0 then return 1 end
    if $Memo[m] != nil then return $Memo[m] end
 
    ret = 0
 
    x = n
    if m < n then x = m end
 
    for i in 1..x
        ret += solve(m-i, n)
    end
 
    $Memo[m] = ret
    return ret
end
 
# main
while line = gets
    line.strip!
    if line.empty? then next end
    m,n = line.split.map{|a| a.to_i}
 
    p solve(m,n)
end

解説

☆3つの問題ですがそれほど難しくありません。
というか、メモ化再帰の例に出てきそうな問題です。

考え方

基本的には再帰で簡単にできます。
例の場合だと、
m=5から1〜3人（最大はnかmの少ない方）がゴンドラに乗ったとする。
1人が乗った場合はm'=4、2人が乗った場合はm'=3、3人が乗った場合はm'=2として同様に1〜3がゴンドラに乗ったとする。
以下同様に繰り返す。
というふうにすればできます。

ただ計算量が多くなるのでメモ化して計算量を減らします。
あるmに対してパターン数が決まっていれば同じmに対しては計算の必要がないのでmをキー、パターン数を値でメモを作成すればOKです。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(m,n)

まず、mが0ならそれ以上パターンを作れないので1を返します。
$Memoに結果があれば計算せず$Memoの当該パターン数を返します。

ゴンドラに乗れる人数xはmかnの小さい方なのでそれを選びます（11〜12行目）。

1〜xまでをゴンドラに乗せ、残りの人数について同様にsolve()を再帰的に呼び出して処理します（14〜16行目）。

結果が求まったら$Memoに記録し、同時に結果を返します。

雑感

数学的に難しいわけでもコードが長くなるわけでもないので何で☆☆☆だったんでしょう。
この出題者の問題だとメモ化再帰とか動的計画法は珍しくないのでそれが理由で難しいと判断されたわけではないと思うのですが。