株式会社アイリッジのクイズに挑戦

採用テスト

トレーディングカードコンプリート問題

100万種類のトレーディングカードがあり、15枚1セット525円で販売されています。全ての種類をコンプリートするまで買い続けるとき、かかる費用の期待値はいくらになるでしょうか。ただし、1セットには全て重複なしのバラバラのカードがランダムに入っているものとします。答えは小数点以下を切り捨てて整数で求めてください。

http://iridge.jp/recruit/quiz/

Google Code Jam 2009 Round 1Aに類題があります．
以下のことを利用して計算します．

1. 現在の種類数をxとしたとき種類数がyに増加する確率T(x, y)は以下のA*B/Cになります．
   1. A:100万種類のうちまだ得ていないもの(1000000 - x)から増加分(y - x)を選ぶ組み合わせの数
   2. B:すでに得ているもの(x)から残りの枚数(15 - (y - x))を選ぶ組み合わせの数
   3. C:100万種類から15枚選ぶ組み合わせの数
2. 現在の種類数がx枚の時の必要なパック数の期待値E(x)はyをxからx + 15に変化させた時のT(x, y) * E(y)の総和に1を足したものになります．
   1. ただし総和の中にE(x)を含むので左辺に移項して係数で割る必要があります．

ソースコード

# -*- coding: utf-8 -*-
import scipy.misc as scm

#種類数
C = 1000000
#一度に得られる枚数
N = 15

#xが増加前の種類数，yが増加後
def T1(x, y):
  return scm.comb(C - x, y - x, 1) * scm.comb(x, N - (y - x), 1)

T2 = scm.comb(C, N, 1)


E = [0] * (C + 1)
E[C] = 0

for i in xrange(C - 1, N - 1, -1):
  E[i] = T2
  for j in xrange(i + 1, min(i + N + 1, C + 1)):
    E[i] += E[j] * T1(i, j)
  E[i] /= float(T2 - T1(i, i))

#費用
print int((E[N] + 1) * 525)