Hatena::Grouptopcoder

SRM diary(Sigmar)

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

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

SRM526.5 Div1 250 MagicCandy

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

Problem Statement

解答方針

これは難しい・・・

最近の簡単な250とは一線を画す問題だな

よく分からんので適当にシミュレーションしたら明らかな法則が出てきたのでとりあえずそれで通った


しかしこういうよく分からんままに通すのはとても良くない。

合っているかどうかの検証もちゃんとできないし、力がつかないと思う。

(とりあえずその場しのぎで通すだけならアリだけど後で理解して解きなおしたほうが良さそう)


Editorialによれば、何ターンで終わるかを最初に計算して、逆順でシミュレーションすることで解を出せるとのこと。

逆順のシミュレーションについては二分探索が使える。

なるほど。。何か250にしては難しいような・・・

他にも色々解き方があるようです。


ソースコード

シミュレーションによって導きだした法則による。

なぜこれでいいのかよく分からない解法

class MagicCandy {
public:
	int whichOne(int n) {
		int res;

		ll t=1;
		while(t*(t+1)+1<=n) t++;
		if(n<t*(t+1)+1-t) res=t*(t+1)+1-2*t;
		else res=t*(t+1)+1-t;

		return res;
	}
};

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