TopCoder SRM 747 Div1 Medium TieForMax

うーん、なんでこれ落ちたんだ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15237

問題

T個のトークンをP人に配ることを考える。
各トークン、等確率でP人のいずれかに配られる。
最多トークンを得た人数がタイ、すなわち２人以上になる確率を求めよ。

解法

以下を考える。
dp(n, t, m, b) := n人目までトークンを配ったところ、残りトークンはt個で、そこまでの最多トークンを得た人のトークン取得数はm、また同着が２人以上いるかどうかの真偽値をbであらわしたときの、そのような状況の組み合わせ

dp(0,T,0,0)から初めて、dp(P,0,*,*)を求めていこう。
あり得る配り方は全体でsum(dp(P,0,*,*))通りあるうち、sum(dp(P,0,*,true))がタイである状況なので、その比率が解。
配り方を考える際Combinationを掛ける必要がある点に注意。

long double comb(int P_,int Q_) {
	static const int N_=1020;
	static long double C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}
long double hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

long double dp[51][51][51][2];


class TieForMax {
	public:
	double getProbability(int t, int p) {
		
		ZERO(dp);
		dp[0][t][0][0]=1;
		int i,j,k,l,b;
		FOR(i,p) {
			FOR(j,t+1) FOR(k,t+1) FOR(b,2) if(dp[i][j][k][b]) {
				FOR(l,j+1) {
					if(l>k)       dp[i+1][j-l][l][0]+=dp[i][j][k][b]*comb(j,l);
					else if(l==k) dp[i+1][j-l][k][1]+=dp[i][j][k][b]*comb(j,l);
					else if(l<k)  dp[i+1][j-l][k][b]+=dp[i][j][k][b]*comb(j,l);
				}
			}
		}
		
		double ok=0,tot=0;
		FOR(k,t+1) {
			ok+=dp[p][0][k][1];
			tot+=dp[p][0][k][0]+dp[p][0][k][1];
		}
		
		return ok/tot;
		
	}
}

まとめ

なぜこんな単純な問題を回りくどい解法して落としたのか…。