TCO2011 Qual1-A 500pt: FoxListeningToMusic

keyword

動的計画法　C++

問題概要

正整数列X(長さN<50, x[i]

解法

dp[i] = {iが端点になっている確率}とすれば、これはO(T*N)で求められる。その後、i+X[i]>=Tとなる確率を足し上げていけばよい。全体の計算量はO(T*N)。

感想

dp[i][k] = {iが棒kの右端になっている確率}としてO(T*N^2)だとギリギリTLEする。最大ケースは{1..1},80000だと思っていたけど(これならTCのサーバー上で通る)、多分キャッシュの関係で{1..1,80000},80000の方が重い。
追記：遅いのはキャッシュのせいではなく非正規化数のせいだった。

vector <double> getProbabilities(vector <int> length, int T) {
	int N = length.size();
	double p = 1.0/N;
	vector<double> dp(T+2,0);
	dp[0] = 1.0;
	for(int t=0; t<=T; t++){
		for(int i=0; i<N; i++){
			dp[min(T+1, t+length[i])] += dp[t]*p;
		}
	}
	vector<double> ret(N,0.0);
	for(int t=0; t<=T; t++){
		for(int i=0; i<N; i++)if(t+length[i] >= T+1){
			ret[i] += dp[t]*p;
		}
	}
	return ret;
}

TLE解

class FoxListeningToMusic {
public:
vector <double> getProbabilities(vector <int> length, int T) {
	int N = length.size();
	double p = 1.0/N;
	vector< vector<double> > dp(T+2, vector<double>(N,0.0));
	dp[0][0] = 1.0;
	for(int i=0; i<=T; i++){
		for(int j=0; j<N; j++){
			for(int k=0; k<N; k++){
			int nt = min(T+1, i+length[k]);
				dp[nt][k] += dp[i][j]*p;
			}
		}
	}
	return dp[T+1];
}