card complete problem implementation -- http://iridge.jp/news/20111220/

cardComplete.scala

object CardComplete {

  def main(args: Array[String]) {
    val calcargs = inquiry()
    //val calcargs = (1000000,15,525)
    val start = System.currentTimeMillis
    calculate(calcargs._1, calcargs._2, calcargs._3)
    val end = System.currentTimeMillis
    println("(in %s sec)".format((end - start) / 1000.0))
  }

  def inquiry() = {
    val sc = new Scanner(System.in)
    print("カードは全部で何種類?: ")
    val totalTypes = sc.nextInt
    print("1パックあたり何枚?: ")
    val typesInAPack = sc.nextInt
    print("1パックの値段?: ")
    val price = sc.nextInt
    (totalTypes, typesInAPack, price)
  }

  def calculate(n: Int, k: Int, price: Int) {
    val comb = cachedCombination(n, k)
    val exp = new Array[Double](n + 1)
    for (i <- 1 to n) {
      /**[解法]
       * カードの総種類をn、1セット当り重複なくk種類のカードが含まれる。
       * iはこれから集めるべきカードの残り枚数を表す。
       * exp(i)は残りi種類集めるときの期待購入セット数を表す。
       * mClはcomb(m, l)メソッドの簡易表記とする。
       * いまn-i種類収集済みで、あと残りi種類必要であるとする。
       * 追加で1セット購入したとき、事後的な可能な残り枚数はi,　... , i - k(>=0)となる。
       * 1セット購入してj(0 ~ k)種類追加的に集まって、残i-j種類になる確率は
       * P(j) = n-iCk-j * iCj / nCk
       * (外れカードk-jの組み合わせ * 当りjの組み合わせ / すべての組み合わせ)
       * であり、exp(i)はこのような可能なj(0 ~ k)によって、P(j)とexp(i-j)を用いて
       * 再帰的に期待値表現することができ、
       * exp(i) = 1 + Σ　P(j) * exp(i - j) [0 <= j <= k]
       *        = {1 + Σ P(j) * exp(i - j) } / (1 - n-iCk / nCk) [1 <= j <= k]
       * と表現できる。
       * ここで、右辺の分母はj = 0のときの、
       * P(0) = n-iCk-0 * iC0 / nCk  * exp(i) = n-iCk / nCk * exp(i)
       * を左辺のexp(i)と整理したものである。
       * exp(0) = 0であるため、i = 0からnへ逐次計算結果をキャッシュすることで
       * exp(i - j)にキャッシュを利用でき、またcombメソッドも再起的に定義したため
       * クロージャによってキャッシュを利用して計算負荷の短縮を行った。
       * すべてのセットをそろえるための購入数の期待値はexp(n)となり、
       * 求める答えはこれにpriceをかけて丸めたものとなる。
       * 以下の実装は除算を削減するために数式を若干変形する。
       * exp(i) = {nCk + Σ P(j) * exp(i - j) * nCk } / (nCk - n-iCk)
       *        = {nCk + Σ (exp(i - j) * n-iCk-j * iCj)} / (nCk - n-iCk)
       */
      val limit = if (i < k) i else k
      var temp = comb(n, k)
      for (j <- 1 to limit) {
        temp += exp(i - j) * comb(n - i, k - j) * comb(i, j)
      }
      exp(i) = temp /  (comb(n, k) - comb(n - i, k))
    }
    val totalPrice = price * exp(n)
    println("TotalPrice: " + totalPrice.toInt.toString)
  }

  def cachedCombination(n: Int, k: Int): (Int, Int) => Double = {
    //in scala2.8
    //val cache = new Array[Array[Double](n+1, k+1)
    val cache = Array.ofDim[Double](n + 1, k + 1)
    for (i <- 0 to n) for(j <- 0 to k)cache(i)(j) = -1
    
    def comb(n: Int, k: Int): Double = {
      /**
       * Ref: http://en.wikipedia.org/wiki/Combination
       * nCk = 1.0 for k = 0, n = k
       * nCk = 0.0 for n < k
       * nCk = nCn-k for n < 2k
       * nCk = n-1Ck-1 + n/k for n,k > 0
       */
      if (cache(n)(k) != -1) cache(n)(k)
      else if (k == 0 || k == n) 1.0f
      else if (n < k) 0.0f
      else if (2 * k > n) comb(n, n - k)
      else {
        val result = n.toDouble / k * comb(n - 1, k - 1)
        cache(n)(k) = result
        result
      }
    }
    comb
  }
}

なるほどー。僕は逆にコンピューターサイエンスの素養が全くないので、ゼッツさまのようなテクニックはまったく思いつかず、
ほとんど紙と鉛筆で考えて、ついでにWikipediaの組み合わせのとこをカンニングしたら奇跡的にメモアイズが効いて
解けたと記憶しています。一年越しのレスでいまさらですが。。