「 今週のお題：どの会場でも均等にセミナーを受講して！」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

• 複数の会場でセッションを開催する際に、以下のような条件のセッションの受講の仕方が何通りあるかを求め、出力する。
• どの会場でも同じコマ数セッションを受講する
• 同一のコマ ( 時間帯 ) で受講できるセッションは高々1つ
• 受講しない時間帯があっても良い。全く受講しなくても良い ( それも「0コマずつ」ということで1通りに数える )
• 会場数 ( 同時開催するセッション数 ) m と、コマ数 n はカンマ区切り1行で入力される。

なお、全く受講しないケースも1通りに数えるのですが、m=n=0 の場合は0通りということで、ここだけはちょっとイレギュラーでした。

解説

以下のRuby(72)を提出しました。

eval"M,N="+gets
a=t=1-1[N]
N.times{|k|a+=1[-~k%M]*t=t*(N-k)/-~(k/M)}
p a

例として、$m=3,\,n=7$ の場合を見ていきます。

各会場で受けるセッション数 k は 0～2回となりますが、k=2 の場合、以下の図のように組み合わせ C での計算が出てきます。

なので、このケースは ${}_7C_{2}\times{}_5C_{2}\times{}_3C_{2}$ 通りと計算できます。

これを変形すると、 $$ \begin{eqnarray} &\,&\frac{7\times 6}{2\times 1}\times\frac{5\times 4}{2\times 1}\times\frac{3\times 2}{2\times 1} \\ &= &\frac{7\times 6\times 5\times 4\times 3\times 2}{2\times 1\times 2\times 1\times 2\times 1} \\ &= &\frac{{}_7P_{6}}{2!^3} \end{eqnarray} $$

答えは、各kでの合計なので、 $$ \frac{{}_7P_{0}}{0!^3}+\frac{{}_7P_{3}}{1!^3}+\frac{{}_7P_{6}}{2!^3} $$ 一般のm,nとしては次のような式になります。( ただし $n=m=0$ の場合を除く ) $$ \sum_{0\le mk\le n}^{}\frac{{}_nP_{mk}}{k!^m} $$

ただ、実装としては、 $$ \begin{eqnarray} &\, &(7&)\div&(1&)& \\ &\, &(7\times 6&)\div&(1\times 1&)& \\ &\star&(7\times 6\times 5&)\div&(1\times 1\times 1&)& \\ &\, &(7\times 6\times 5\times 4&)\div&(1\times 1\times 1\times 2&)& \\ &\, &(7\times 6\times 5\times 4\times 3&)\div&(1\times 1\times 1\times 2\times 2&)& \\ &\star&(7\times 6\times 5\times 4\times 3\times 2&)\div&(1\times 1\times 1\times 2\times 2\times 2&)& \\ &\, &(7\times 6\times 5\times 4\times 3\times 2\times 1&)\div&(1\times 1\times 1\times 2\times 2\times 2\times 3&)& \end{eqnarray} $$ のように、分母・分子を増やしながら計算していく中で、$\star$の付いたところの値を加算していくようにします。
これにより、n回のループの中でm回おきに加算するようにして求めることができます。 なお、k=0 の時の場合の数 1 は初期値としてセットしておきます。

終わりに

naiveに階乗等を実装すると多重ループになるところ、1重ループにできるとちょっと嬉しいところですね。