CodeIQ 挑戦の記録 : 第82回「今週のアルゴリズム：どの会場でも均等にセミナーを参加して！」
CodeIQというサイトで問題に挑戦した記録です。
問題文を要約すると下記の通り
- あるセッションのタイムテーブルの参加パターンを考える
- 同時間帯にm個の会場でセッションが行われ、nコマあるとする
- どの会場へも同じ回数で参加するとすると、参加パターンは何パターンあるか解答する。
- 全く参加しないパターンも含む
方針
組み合わせの問題として考える。
それぞれの会場で参加するセッションの回数は同じにする必要があるので、それぞれの会場で参加する回数をp回とするとpの取りうる範囲は
\( 0 \le p \le floor(n \div m) \)
会場1から会場mのそれぞれについて、
- 会場1では\(n \)回のセッションの中から\(p \)回を選ぶ事ができる。
- 会場2では\(n \)回から会場1で選んだ\( p\)回を除いた\( (n-p) \)回から\(p \)回を選ぶ。
- 同様に会場3では\((n-2p)回からp \)回を選ぶ・・・
これを全ての会場分について掛けたものが一つの会場で\(p \)回参加する場合のパターン数となる。
つまり、組み合わせ\( _nC_k \) を用いて、
これをpについて1から\( floor(n \div m) \)まで計算したものを加算し、全く参加しない1パターンを加えて解答とする。
実装
提出したコードか下記の通り(Ruby)
Sponsored Link
