kmjp's blog

競技プログラミング参加記です

TopCoder SRM 822 : Div1 Easy Div2 Hard ProbabilisticStreamMinimum

問題読み解くのに苦労した。
https://community.topcoder.com/stat?c=problem_statement&pm=17371

問題

N個のアイテムあり、それぞれ異なるパラメータを持つ。
このうち、パラメータの小さい順K個を抽出する以下のアルゴリズムを考える。

K^2個のバケットを持って置く。
アイテムを1個ずつ見て行き、ランダムなバケットを割り当てよう。
もしバケットが空であるか、パラメータの大きなアイテムが入っている場合、代わりに今見ているアイテムを入れる。

最終的に、K^2個のバケット中に、パラメータの小さい順K個が入っている確率を求めよ。

解法

パラメータの小さいK個が、それぞれ異なるバケットに割り当てられれば良い。
よって \displaystyle \frac{K^2}{K^2} \cdot \frac{K^2-1}{K^2} \cdots \frac{K^2-(K-1)}{K^2}が解。
以下のコードでは念のため対数を取って計算したが、その必要もなかった様子。

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);
	}
}

まとめ

計算内容の割に無駄に問題が長くてなぁ。