Skip to content

Instantly share code, notes, and snippets.

@keitaoouchi
Last active September 16, 2016 16:06
Show Gist options
  • Save keitaoouchi/2381408 to your computer and use it in GitHub Desktop.
Save keitaoouchi/2381408 to your computer and use it in GitHub Desktop.
card complete problem implementation -- http://iridge.jp/news/20111220/
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
}
}
@keitaoouchi
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment