MemSQL start[c]up 2.0 Round 1 : C. Magic Trick

N種類のカードが１枚ずつあるカードデッキがあり、同じデッキがM組ある。
これらのN*M枚のカードからN枚を選択して新たなデッキを作る。

この新デッキから１枚カードを選んでカードを覚える。
カードを戻して再度デッキからカードを１枚選んだ時、元と同じカードである確率を求めよ。

O(N^2*M)のDPも考えられるが、実はO(1)で解ける。

１枚のカードを２回選ぶとき：

元と同じカードを選ぶ確率は $\frac{1}{N}$
元と別のカードを選ぶ確率は $\frac{N-1}{N}$ で、そのカードが元と同じ種類である確率はN*M枚から元のカードを除いた1枚からM-1枚の同種カードを選ぶ確率なので $\frac{N-1}{N}\times\frac{M-1}{NM-1}$

よって両者を合わせて $\frac{1}{N} + \frac{N-1}{N}\times\frac{M-1}{NM-1} = \frac{NM-1+(N-1)*(M-1)}{N(NM-1)}$ である。

注意点としてN==M==1の時、分母が0となる。
これはカードが１枚しかないのでそもそも「元と別のカードを取る」というケースがないためである。
ただしこの場合確率は明らかに1なので気にしなくてよい。

ll N,M;

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	if(N*M==1) return _P("1\n");
	_P("%.12lf\n",(double)((N*M-1)+(N-1)*(M-1))/(N*(N*M-1)));
}

最初DPで間に合わない…と頭を抱えていたのに、意外とあっさり。

kmjp's blog