私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「パターゴルフのコース設計」（CodeIQ）を参照してください。
パターゴルフのコースを新しく作ることにしました。
そこで、各ホールの標準打数を考えています。
m ホールで合計の標準打数が n になるように、各ホールの標準打数を決めなければなりません。
なお、各ホールの標準打数は1以上5以下とし、m≦18とします。
例えば、3ホールで合計が12の場合、以下の10通りがあります。
2 5 5
3 4 5
3 5 4
4 3 5
4 4 4
4 5 3
5 2 5
5 3 4
5 4 3
5 5 2
標準入力から m と n がスペースで区切って入力されます。
このとき、各ホールの標準打数のパターン数を標準出力に出力してください。
【入出力サンプル】
標準入力
3 12
標準出力
10
Rubyで解答しています。
#!/usr/bin/ruby
# 1ホールだけの場合は1..5の範囲が1なので[0,1,1,1,1,1,0,0,...]を作って返す
def init(m)
ret = Array.new(m*5+1, 0)
for i in 1..5
ret[i] = 1
end
return ret
end
# i-1ホールのパターンからiホールの場合のパターンを作る
def getNext(base, i, m)
ret = Array.new(m*5+1, 0)
for j in i..(i*5)
min = j-5 < 1 ? 1 : j-5
cnt = 0
(j-1).downto(min){|k|
cnt += base[k]
}
ret[j] = cnt
end
return ret
end
# 問題を解く
def solve(m,n)
patterns = [Array.new(m*5+1, 0)] # 行はホール数、列はトータルの打数
patterns << init(m) # 1ホールの場合の値を作る
for i in 2..m
ret = getNext(patterns[i-1], i, m)
patterns << ret
end
return patterns[m][n]
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
このシリーズの出題者の最近の問題の中ではやや簡単です。
それでも十分難しいですが。
18ホールもあるのでパターン数が大変な数になります。実際にパターンを列挙していては絶対に間に合いません。なのでパターン数だけを数える必要があります。
まず、m=1の時を考えてみます。
この時のパターン数は要素番号を標準打数とすると[0,1,1,1,1,1]の配列として表現できます。つまり、(m,n)=(1,0)なら標準打数は0、(m,n)=(1,1〜5)は1ホールしかないのでそれぞれの標準打数のパターン数は1、(m,n)=(1,6〜)は最大5打なので0です。
まず、m=2の時にどうなるでしょうか？
標準打数が2の場合、第1ホールが1なら第2ホールが1のパターンしかありませんから1パターンだけです。
標準打数が3の場合、第1ホールが1なら第2ホールは2、第1ホールが2なら第2ホールは1の2パターンがあるので2パターンです。
標準打数が4の場合は第1ホールが1なら第2ホールは3、第1ホールが2なら第2ホールは2、第1ホールが3なら第2ホールは1の3パターンです。
同様にn=10（m=2の場合の最大値）まで考えると次のようになります。
[0,0,1,2,3,4,5,4,3,2,1]（標準打数は0始まりなので11個ある）
これをm=1の時のと要素数を揃えて並べてみます。
| 標準打数 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||
| m | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | |
これを一般化すると、
第i（iは1〜m）ホール目の標準打数kのパターン数は第(i-1)ホールの標準打数(k-5)〜(k-1)までのパターン数の合計
となります。
念のためm=3をこの考え方に基づいてやってみます。
| 標準打数 | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
| m | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 0 | 1 | 2 | 6 | 10 | 15 | 18 | 19 | 18 | 15 | 10 | 6 | 2 | 1 | |
第1ホールのパターンを作ります。
第1ホールのパターンは一つ前のパターンから計算できないので作ってしまいます。
結果は要素数がm*5+1個の配列で、要素番号0と6以降は0埋めしています。
標準打数が大きい方（6以降）をわざわざ0埋めして作っているのは以降の計算で領域外のチェックを省くためです。例えば(m,n)=(2,7)の時に(m,n)=(1,6)を参照しますが0をセットしてあるので単純に計算に含めればよくなるのでプログラムが簡単になります。
考え方に示した表のi番目の行を(i-1)番目の結果から計算します。
引数baseは(i-1)行目のパターン数、iは計算対象の行数、mは入力値です。
i行目の標準打数はi（全ホール1打）〜(i*5)（全ホール5打）までのパターンが考えられますのでそれだけのパターンループします（16〜23行目）。
大きい方の領域外は余分に領域をとって0埋めしていますが、小さい方はそういうことをしていないのでチェックします（17行目）。
ループカウンタ-1〜-5（最低1）まで(i-1)番目のパターン数を合計します（19〜21行目）。
結果をi行目のループカウンタの標準打数の位置に記録します（22行目）。
最終的に結果の配列を返します。
問題を解きます。
引数m,nは入力値です。
patternsは0〜mホールまである場合の各標準打数のパターン数を記録する2次元配列です。
ホール数は1始まりなのでpatternsの要素番号0の行は全部0の配列を入れておき、要素番号とホール数を一致させます（30行目）。
ホール数1の場合のパターンを初期値として設定します（31行目）。
ホール数2〜mまで順番に取り得る標準打数全てのパターンに対してパターンを計算し、patternsに追加します（33〜36行目）。
patterns[m][n]が答えになるのでこれを返します。
どうも、この手のパターン数を求めるタイプの問題は苦手です。
話は全然変わりますが、「自然数nをk以下のちょうどm個の数に高速に分割する（分割のパターン数を求める）」方法があれば簡単に解ける問題が結構多いのです。この問題もそうです。いつも探しては見るのですが見つかりません。知っている人がいたら教えて欲しいです。できれば分割後の数値に重複を許す場合と許さない場合でそれぞれ別に。