Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-06Google Code Jam 2012 Round 1A

Google Code Jam 2012 Round 1A A Password Problem

| 20:30 | Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) Google Code Jam 2012 Round 1A A Password Problem - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

最初のi個が連続して正しい確率を求めて、何個バックスペースを使うと最も期待値が小さいか調べて、その最小値を返すだけ

なんだけど、色々こまごました式で混乱してしまって20分くらい使ってしまった

終わっとる・・・


ソースコード

入力のパースは省略

double solve(int A, int B, vector <double> &p) {
	double res=0;
	
	vector <double> pn;
	double cp=1;
	for(int i=0; i<A; i++) {
		cp*=p[i];
		pn.push_back(cp);
	}

	res=B+2;
	for(int i=A; i>0; i--) {
		double curk=(A-i)+(B-i+1)+(1-pn[i-1])*(B+1);
		res=min(res, curk);
	}

	return res;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120506