問題読み解くのに苦労した。
https://community.topcoder.com/stat?c=problem_statement&pm=17371
問題
N個のアイテムあり、それぞれ異なるパラメータを持つ。
このうち、パラメータの小さい順K個を抽出する以下のアルゴリズムを考える。
K^2個のバケットを持って置く。
アイテムを1個ずつ見て行き、ランダムなバケットを割り当てよう。
もしバケットが空であるか、パラメータの大きなアイテムが入っている場合、代わりに今見ているアイテムを入れる。
最終的に、K^2個のバケット中に、パラメータの小さい順K個が入っている確率を求めよ。
解法
パラメータの小さいK個が、それぞれ異なるバケットに割り当てられれば良い。
よってが解。
以下のコードでは念のため対数を取って計算したが、その必要もなかった様子。
class ProbabilisticStreamMinimum { public: double calculate(int N, int K) { double a=0; int i; for(i=1;i<=K;i++) { a+=log(K*K+1-i); } a-=K*log(K*K); return exp(a); } }
まとめ
計算内容の割に無駄に問題が長くてなぁ。