Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-10SRM536 Div1

SRM536 Div1 250 MergersDivOne

| 11:45 | SRM536 Div1 250 MergersDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM536 Div1 250 MergersDivOne - SRM diary(Sigmar) SRM536 Div1 250 MergersDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

一瞬DPかと思ってちょっと時間を無駄にしてしまった

しかしよく見るとどう見ても小さい方から2つずつくっつけていけば最適っぽい

こういうGreedyなのって急ぐとろくなことがない。落ちる可能性が高い。

少し考えてみるが、反例が思いつかない。大丈夫な気がする。

提出。

プログラミングというより数学の問題ですね


ソースコード

class MergersDivOne {
public:
	double findMaximum(vector <int> rev) {
		double res;
		int n=rev.size();
		sort(rev.begin(), rev.end());

		res=rev[0];
		for(int i=1; i<n; i++) res=(res+rev[i])/2;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120310