Codeforces #399 D. Jon and Orbs

想定解なのかな…？
http://codeforces.com/contest/768/problem/D

問題

K種類のオーブがあり、全部をそろえたい。
1日に1個のオーブが等確率でいずれか手に入る。

数列P[i]に対し、n日後に全種類のオーブが最低1個ずつは保持している状態になる確率がP[i]/2000を超える最小のnを答えよ。

解法

以下を考える。これはO(ab)のDPで埋めることができる。
f(a,b) := a日後に持っているオーブの種類がb種である確率

そうするとf(n,K) ≧ P[i]/2000となる最小のnを求めればよいことになる。

幸い、P[i]の上限は1000、つまり50%の確率で揃えばよい。
実際f(a,b)を求めてみると、最大ケースのK=1000でも7300回足らずで50%を超える。
よってf(1000,7300)までf(a,b)を埋めればよくこれはO(ab)のDPで十分間に合う。

int K,Q;
int P[10101];
double PP[8000][1050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>Q;
	
	PP[0][0]=1;
	FOR(i,7300) {
		FOR(j,K+1) {
			PP[i+1][j]   += PP[i][j]*j/K;
			PP[i+1][j+1] += PP[i][j]*(K-j)/K;
		}
	}
	
	FOR(i,Q) {
		cin>>x;
		for(j=0;j<=7300;j++) {
			if(PP[j][K]>=x/2000.0-1e-9) {
				cout<<j<<endl;
				break;
			}
		}
	}
	
	
}

まとめ

こんな愚直な方法は想定解なのか…？