Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-15TCO2011 Qual1

TCO2011 Qual1 500 FoxListeningToMusic

| 14:25 | TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何となく、曲の終わるタイミングが時間tである確率をDPすれば良さそうである

書いた

サンプル合った

提出


ソースコード

class FoxListeningToMusic {
public:
	vector <double> getProbabilities(vector <int> len, int T) {
		vector <double> res;
		int n=len.size();
		res.assign(n, 0);

		double dp[80010];
		memset(dp, 0, sizeof(dp));
		dp[0]=1;
		for(int t=0; t<=T; t++) {
			for(int i=0; i<n; i++) {
				if(t+len[i]>T) res[i]+=dp[t]/n;
				else dp[t+len[i]]+=dp[t]/n;
			}
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110515