Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-19TCO2011 Round1

TCO2011 Round1 500 MuddyRoad

| 17:19 | TCO2011 Round1 500 MuddyRoad - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round1 500 MuddyRoad - SRM diary(Sigmar) TCO2011 Round1 500 MuddyRoad - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは、次がmuddyであれば、その次がmuddyかどうかに関わらず、ジャンプしたほうが良いよね

(そのほうが早く連続するmuddyの区間を抜けられるから)

それから、次がmuddyでなければ、無条件にそこを通れば良いよね

(muddy区間のぎりぎり手前でジャンプしたほうが良いだろうから)

という戦略に基づいて、道iを通る確率をdpで求める

で、道iにいるときに、次とその次が両方ともmuddyだった場合のみ、muddyの道を通ることになるわけだ

ということでコーディングする

サンプル合った

比較的すぐ解けた!いい感じ。


ソースコード

class MuddyRoad {
public:
	double getExpectedValue(vector <int> road) {
		double res=0;
		int n=road.size();

		double dp[52];
		memset(dp, 0, sizeof(dp));
		dp[0]=1;
		for(int i=0; i<n-2; i++) {
			dp[i+1]+=dp[i]*(1.-(road[i+1]/100.));
			dp[i+2]+=dp[i]*(road[i+1]/100.);
			res+=dp[i]*(road[i+1]/100.)*(road[i+2]/100.);
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110619