私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「どの会場でも均等にセミナーを受講して!」(CodeIQ)を参照してください。
Pythonで解答しています。
#!/usr/local/bin/python3
import fileinput
'''
組み合わせ数を計算する
'''
def C(n,r):
ret = 1
for i in range(n, n-r, -1):
ret *= i
for i in range(r, 1, -1):
ret //= i
return ret
'''
@param n コマ数
@param m セッション数
@return 組み合わせ数
'''
def takeSession(n,m):
# nもしくはmが0の場合、どれも行かないとして1としたが、テストパターンでは0らしい
if (m==0) or (n==0):
return 0
# セッション数がコマ数より多い場合、どれも行かない場合だけしかない
if(m>n):
return 1
t = n // m # 1会場について*最大*何セッション出席すべきか
ret = 0 # 答え
# 各会場を最大t回回ることができる
for i in range(t, 0, -1):
r = n # 残りのコマ数
c = 1 # 各会場をi回まわる場合の組み合わせ数
for j in range(m):
c *= C(r,i)
r -= i
ret += c
# 1つも出席しない場合を加算する
return ret+1
if __name__ == "__main__":
for line in fileinput.input():
if not line.strip():
continue
m,n = map(int, line.strip().split(","))
ret = takeSession(n,m)
print(ret)
この問題は珍しくプログラムでシミュレーションしたりするよりも、数学的に式を考えて解く方が簡単(というか、先に数学的に解くことができた)問題です。
| A会場 | B会場 | C会場 |
|---|---|---|
| A-1 | B-1 | C-1 |
| A-2 | B-2 | C-2 |
| A-3 | B-3 | C-3 |
| A-4 | B-4 | C-4 |
| A-5 | B-5 | C-5 |
| A-6 | B-6 | C-6 |
前述の考え方を一般化して実装したのがこの関数です。
まず、セッションをしていない場合は0を返します。これは問題からは1にすべきか0にすべきかはっきりしなかったのですが0とみなすようです。また、会場数が時間数よりも多い場合は1つもいかないという選択肢しかないので1を返します。
次に、各会場を最大何回回れるのかを計算します(29行目)。これは時間数÷会場数(小数点以下切り捨て)なのは簡単にわかります。最大回数がわかったら1〜最大回数までそれぞれ何通りあるかを求めて足し合わせればOKです。
33行目のループがこの処理にあたります。39行目の足し算は次に説明する各会場を1回、2回、…、回る場合のパターンを足し合わせる処理をしています。
36行目のループは決まった回数(例えば2回ずつ)各会場を回る組み合わせの数を計算します。会場数をn、会場を訪れる回数をxとすると1つ目の会場を訪れるパターンはnCxで、2つ目の会場を訪れる回数はn-xCx、3つ目の会場ならn-2xCx、…で、これを掛け合わせることになります。
このn、n-x、n-2xを計算しているのが38行目で、組み合わせを計算して掛け合わせているのが37行目です。
各会場を1回以上回るパターンの合計に対し、1つも行かない場合の1を加えたのが答えです。
この問題は数学の問題として解くことができて非常にすっきりしました。