Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-12-30SRM526.5 Div1(Practice)

SRM526.5 Div1 500 MagicBlizzard

| 21:20 | SRM526.5 Div1 500 MagicBlizzard - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM526.5 Div1 500 MagicBlizzard - SRM diary(Sigmar) SRM526.5 Div1 500 MagicBlizzard - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

これまた難しい!!

正直言って分からなかった。


Editorialによると、1セルの累積snowball数についてはレンジ内の全セルの平均値を使っても問題ないらしい。

そうすると、平均累積snowball数をxとすると、次のsnowballによる解の増分はどこに降ろうが(x+1)^2-x^2で2x+1となる


他にも分散の公式を使う方法とか。色々あるみたい。

結構数学的な発想を必要とする問題だなと思った。


class MagicBlizzard {
public:
	double expectation(vector <int> range, vector <int> amount) {
		double res=0;

		int n=range.size();
		vector <pair <int, int> > ra;
		for(int i=0; i<n; i++) ra.push_back(make_pair(range[i], amount[i]));
		sort(ra.begin(), ra.end());

		int cnt=0;//累積snowball数の全セルの和
		for(int i=0; i<n; i++) {
			double r=ra[i].first;
			double area=(2*r+1)*(2*r+1);
			for(int j=0; j<ra[i].second; j++) {
				double balls=cnt/area;//1セルの平均累積snowball数
				res+=2*balls+1;
				cnt++;
			}
		}
		return res;
	}
};

TestTest2012/01/05 22:52double area=(2*r+1)*(2*r+1);
j=ra[i].second;
res+=j*(2*cnt+j-1)/area+j;
cnt+=j;

SigmarSigmar2012/01/14 00:40500 MagicBlizzardの最内ループを効率化できるよ、というコメントでしょうか?
ありがとうございます。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111230