私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「整数倍の得票数」（CodeIQ）を参照してください。
参議院選挙が終わったかと思えば、東京都知事選挙。
投票に行ったあとは、誰がどれくらいの得票数を獲得するのか、結果を見るのも重要です。
今回は、最下位の候補者の得票数を1としたときに、ほかの候補者の得票数が整数倍になるようなパターンを考えます。
（候補者は自分自身に投票するため、最低でも1票は確保できるものとします。）
例えば、3人の候補者に対して7人が投票するとき、その得票数のパターンは以下の4通りがあります。
5-1-1
4-2-1
3-3-1
3-2-2
(候補者は区別せず、得票数のみに注目します。)
ここで、3-2-2の得票数は、最下位の候補者を1とするとほかの候補者が整数倍にならないため、対象外です。
つまり、上記の場合は3通りです。
標準入力から m, n の2つの整数が与えられたとき、 m 人の候補者に対して n 人が投票するとき、上記のようなパターンが何通りあるかを標準出力に出力してください。
ただし、 0 < m < n < 80 とします。
【入出力サンプル1】
標準入力
3 7標準出力
3
Rubyで解答しています。
#!/usr/bin/ruby
$Memo = {}
# nをm個以下の数に分割する
# part(m, n-m)とした結果はnをちょうどm個の数に分割した数に等しい
def part(m,n)
if n < 0 then return 0 end
if n < 2 || m == 1 then return 1 end
ret = $Memo[[m,n]]
if ret != nil then return ret end
ret = 0
for i in 1..m
ret += part(i, n-i)
end
$Memo[[m,n]] = ret
return ret
end
def solve(m, n)
mx = n/m # 最小の得票数の最大数
ret = 0
# 最小得票の人の得票数を固定して計算する
# 他の人が最小得票数の整数倍になるのは、(m-最小得票数)/最小得票数を残りの人数で自然数分割したパターン数になる
for i in 1..mx
rm = m - 1 # 他の候補者の数
rn = n - i # 他の人の票の合計
# 最小得票数で残りの票を割った数にあまりがある場合、整数倍にはできない
if rn % i != 0 then
next
end
dn = rn / i
# part(m, n-m)とした結果はnをちょうどm個の数に分割した数に等しい
v = part(rm, dn-rm)
ret += v
end
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
★★の問題ですが非常に難しいと思いました。簡単な★★★★よりも難しかったと思います。
この問題が自然数分割の問題であることに気付き、かつ、どうすればシンプルな自然数分割として扱えるかに気付かない限りできないでしょう。
直前に書いた通り、この問題は自然数分割の問題です。
ただし、全体を一塊に考えて最小の分割数が1の場合、2の場合、……、と場合分けして考えるのは無理です。
鍵となる考え方は最小得票数を分けて考えることです。
例のm=3, n=7ではパターンが少なすぎるのでm=3, n=10の場合を考えます。
この場合、問題の条件に合うのは次の6通りです。
[8,1,1], [7,2,1], [6,3,1], [5,4,1]
[6,2,2], [4,4,2]
ここで[8,1,1]〜[5,4,1]の行に注目します。
一番右の1を取り除いた場合、[8,1], [7,2], [6,3], [5,4]となります。これは9をちょうど2個の自然数に分割した場合の組み合わせ全てになります。
次に[6,2,2], [4,4,2]の右端の2を取り除きます。[6,2], [4,4]ですが、さらに右端の数（2）で割ります。[3,1],[2,2]となり、これは4（=(10-2)/2）をちょうど2個の自然数に分割した場合の組み合わせ全てになります。
つまり、最小得票数をxとした場合、他のメンバーの得票数のパターンは(n-x)/xをちょうど(m-1)個の自然数に分割した場合の組み合わせ数になるわけです。
当然ですが、(n-x)/xが割り切れない場合、あまりの分がどこかに加えられなければならないため誰かの得票がxの倍数になりません。そのため、(n-x)/xが割り切れない場合の組み合わせ数は0になります。
自然数分割を行います。
高速化するためメモ化再帰としていますが、メモを使用しないバージョンは非常にシンプルです。
def part(m,n) if n < 0 then return 0 end if n < 2 || m == 1 then return 1 end ret = 0 for i in 1..m ret += part(i, n-i) end return ret endこれはアルゴリズム事典に乗っている自然数分割のコードらしいです（私はWebで発見しました）。考え方としては、
ただし、part()に入力値のm,nをそのまま適用してもダメです。nをちょうどm個に分割する必要があって、m個以下に分割するのでは間違いです。
これまたよく理解していないのですが、part(m,n-m)とすると、その結果はnをちょうどm個に分割した場合のパターン数になるというのが重要なポイントです。これによって正しい結果を計算できます。
提出したコードのメモ化部分は自分で実装したので説明できますが大したことではありません。キーが[m,n]となる入力値の組み合わせで、値がその計算結果です。すでに計算済みの値があるなら計算を省いて値を返し（11〜12行目）、計算結果がないなら計算して、計算完了後に$Memoに値を記録する（19行目）だけです。
これで問題の入力範囲の最悪くらいのケースで約10倍早くなります。メモ化しないと私のロカル環境でtimeコマンドで計測した場合、part(15,79)で0.45秒くらいかかりますが、メモ化すると0.045秒くらいになります。メモ化しなくても制限時間をクリアできる可能性は高そうですが、やっておいて損はないのでメモ化しました。
最小得票数のパターンごとにパターン数を計算してたし合わせ、結果を返します。
最小得票数の上限まで計算しないといけないですが、これは簡単にわかります。最小得票数の票が最も多くなるのは全体が満遍なく票を獲得した場合なので平均値（端数切り捨て）になるのは明らかです（24行目）。
最小得票数の上限がわかったら1〜上限までを計算します（29〜43行目）。
候補者の数は最小得票者を覗いているのでm-1人になります（30行目）。
最小得票者以外の票の合計は最小得票者の票を除いた分なのでn-iになります（31行目、iは最小得票者の獲得票）。
「考え方」にも書いた通り、残りの票の合計がiの倍数でなければパターン数は0なので無視します（34〜36行目）。
あとは残りの票をiで割ったものをm-1人で分割したパターン数が最小得票者の獲得票がiの場合のパターン数になるのでpart()で計算し、結果を合計します。繰り返し書きますがpart(m,n-m)がnをちょうどm個の自然数に分割した時のパターン数になるので、そのようにパラメータを渡します（38〜42行目）
最終的に合計値を返せば答えになります。
最初にも書いた通り非常に難しかったです。10時間あまりかかりました。
最初、★★の問題だし動的計画法でパターンを列挙して条件に合うものを数えてば良いだろうと思って取り掛かったのですが、試しに最悪に近いと思えるパターン（(m,n)=(10,79)や(20,79)）をやってみたら全く計算が終わらない。そのあと6通りもパターンを列挙するコードを書き、かなり無駄なく列挙できるところまで行ったのにもかかわらず時間的には全然ダメ（Ctrl+Cで中断するレベル）。
途中で薄々「パターンだけを数えないとダメかもなぁ」と思っていましたが確信に変わりました。また、「最小得票者の得票数が2以上の場合、他のメンバのパターンは全体を最小得票者の票数で割ると、最小得票者の得票数が1の場合と同じになる」というのは結構早い段階で気づいていましたが、「ある自然数nをちょうどm個に分割し、その最小数がちょうど1のみのもののパターンを数える方法」をどうしようかというので非常に悩みました。
話は変わりますが、CodeIQで出題される問題では経路探索の問題が高レベル（★★★以上）になることが多く、この問題のようにパターン数を数える問題のレベルはそれよりも低めに設定されることが多いように思えます。確かにコード量は経路探索の問題の方が長くなりがちですが、デバッグしやすい（途中の計算結果を記録するのは必須なのでそれをロギングすれば良い）ので、私は経路探索の問題の方が数学的に難しいパターンを数える問題よりもやりやすいと思っています。