Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-23SRM504.5 Div1

SRM504.5 Div1 900 TheTicketsDivOne

| 23:21 | SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

見たところ、無限にDPを繰り返せば答えが出るタイプのよくあるやつにしか見えない

実際には無限に繰り返さず適当に打ち切っても精度的には問題ない

漸化式さえできれば、書くだけ

これこそ550くらいが適正じゃないのか・・・

今度から900が出たら問題くらいは読もう・・・


ソースコード

class TheTicketsDivOne {
public:
	double find(int n, int m) {
		double res;

		memset(dp, 0, sizeof(dp));
		dp[0][1][0]=1;

		for(int turn=0; turn<200; turn++) {
			int cur=turn%2, next=(turn+1)%2;
			memset(dp[next], 0, sizeof(dp[next]));
			for(int cnum=1; cnum<=n; cnum++) {
				dp[next][cnum][0]+=1/6.;
				for(int cidx=0; cidx<cnum; cidx++) {
					dp[next][cnum][(cidx+1)%cnum]+=dp[cur][cnum][cidx]/2.;
					dp[next][cnum+1][cidx+1]+=dp[cur][cnum][cidx]/3.;
				}
			}
			dp[next][1][0]=1;
		}

		res=dp[0][n][m-1];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110523