CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第104回「整数倍の得票数」

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

選挙での候補者数と得票数について、最下位の候補者の得票数を1としたときに、ほかの候補者の得票数が整数倍になるようなパターンについて考える。
例：3人の候補者に対して7人が投票するとき、その得票数のパターンは以下の4通り。
5-1-1
4-2-1
3-3-1
3-2-2
（候補者は区別せず、得票数のみに着目する）
この場合で、3-2-2は最下位の候補者を1とすると他の候補者の得票数が整数倍にならない為対象外。
よって3パターンとなる。
標準入力から ${m,n}$ が与えられ、 ${m}$ 人の候補者に対して ${n}$ 人が投票するときこの様なパターンは何通りあるかを解答する。
${(0 \lt m \lt n \lt 80)}$

方針

メモ化再帰により探索する。
${m}$ 人の候補者に対して ${n}$ 人が投票する場合で、最下位の候補者の得票数を ${b}$ とおくと、その他全ての候補者の得票数が最下位の候補者の得票数の整数倍になるならば、以下が成り立つ。

${n}$ は ${b}$ の倍数である。
最下位の候補者を除く ${m-1}$ 人の得票数の合計は ${n-b}$ 票である。

これより、 ${b}$ を ${1}$ から ${\lfloor {n/m} \rfloor}$ まで、 ${n}$ を割り切る時のみ、題意のパターンをメモ化再帰で探索し、そのパターン数の合計を解答とする。
なお、探索では、全て ${b}$ の整数倍のものを探すので、初めから ${n}$ を ${b}$ で割ったものを調べる事で探索数を減らす事とする。
また、例えば7票を3人で分ける場合で、1-1-5パターンとこれを並び替えた1-5-1、5-1-1は同じパターンとみなすので、重複カウントを防ぐ為に、再帰関数の中で得票数のパターンを昇順のみ探索する様にしている。

実装(Ruby)

では、

Sponsored Link