CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第99回「均等に分配されるカード」

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

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

• m 枚のカードがあり、それぞれに 1～m までの数字が1つずつ書かれている。 これらのカードを n 人に配る時、それぞれの持つカードの数の和が全員同じになる分け方が何通りあるかを求める。
• 

方針

メモ化再帰を用いる。
組み合わせ論的に考えようとしたが良い方法が思いつかなかったので、再帰で探索する事にした。
1からmまでの数値を全ての組み合わせについて加算していき、1からmまでの総和 をnで割った 1人に配る数の和sumに一致すれば和の組iを加算する。
iがnに一致すれば1通りとし、総数を数える。
カードの数値の組はビット演算でフラグとする。

反省

• 自分が改めてメモ化がヘタクソだと思った。
  提出したメモ化では高速化の効果は少ないと思いながら書いたが、案の定メモ化でありながら最大のケースで 約0.4秒近くかかった。
• 1回WAであった。
  原因はすぐ分かった。解答は組み合わせではなく順列だった。
  重複なく数え上げるアルゴリズムは思いつかなかったので、不本意ながら最終的に解答をの階乗で割って解答とした。
  (1を含む組のみ最初に固定して組み合わせを作ったので、n組から1を引いた個数の順列)

実装(Ruby)

では、


Sponsored Link