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;
	}
};

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