Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-03-20SRM500 Div1

SRM500 Div1 250 MafiaGame

| 14:49 | SRM500 Div1 250 MafiaGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM500 Div1 250 MafiaGame - SRM diary(Sigmar) SRM500 Div1 250 MafiaGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

問題文長すぎかつ読解難易度高い

平均得点が低いのはこの分かりにくい問題文の影響に違いない

何回か読んで意味を理解したので何となくシミュレーションのコードを書いてみる

普通にシミュレーションしても最大投票数を獲得した人が複数いる場合の確率が出せない

色々考える

ああ、そうか。1ラウンド目でdecision内の投票が終わったあと、残りの人は必ず0票の人に投票するから、

すでに1票以上獲得している人がそれ以上の票を獲得することはない。

ということは、1ラウンド目で最大投票獲得の人たち以外は全員消滅する。

あとは全員当選確率は等確率であるはずだから、無限ループするかのチェックをするだけだ。シミュレーション必要ない。

気をつけるのは、decision内で最大投票獲得が1票だった場合は、decision外も含め全員1票なので必ず無限ループする。

無限ループするかのチェックは、、えーと、、サンプル見る限りN%2==0で無限ループかな(←間違い)

サンプル合った→提出

合ってるかな・・

・・・

・・・

無限ループのチェック、間違ってるな・・・

どう見てもN%2==0の条件じゃない。10,{0,1,2,0,1,2}とかだと無限ループしないじゃないか。

Nを最大投票獲得者数で割った余りを次ラウンドのvulnerableな人数とするのが正しいぽい。

最終的にNがvulnerableな人数で割り切れると無限ループ、余りが1になると収束。

余りをとると、vulnerable人数は1以上減っていくので、必ず収束する。

修正→再提出

終わったな・・・


ソースコード

class MafiaGame {
public:
	double probabilityToLose(int N, vector <int> dec) {
		int n=dec.size();

		vector <int> cnt(N, 0);
		for(int i=0; i<n; i++) cnt[dec[i]]++;
		int maxcnt=0;
		for(int i=0; i<N; i++) if(cnt[i]>maxcnt) maxcnt=cnt[i];
		if(maxcnt==1) return 0;
		int maxcntcnt=0;
		for(int i=0; i<N; i++) if(cnt[i]==maxcnt) maxcntcnt++;
		if(maxcntcnt==1) return 1;

		int t=maxcntcnt;
		while(1) {
			int rem=N%t;
			if(rem==1) return 1./maxcntcnt;
			if(rem==0) return 0;
			t=rem;
		}
	}
};

SRM500 Div1 500 FractalPicture

| 14:49 | SRM500 Div1 500 FractalPicture - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM500 Div1 500 FractalPicture - SRM diary(Sigmar) SRM500 Div1 500 FractalPicture - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

既に残り35分くらいしかなく、無理そうな雰囲気が漂う

やっぱりEasyに時間かけるとEasyの点低いわMedium解く時間ないわで悪循環が生まれますね・・

読んだところMediumらしからぬほど方針は簡単そう。要するに書き方が難しく、いかに

バグのなさそうな書き方ができるかどうかにかかっている、実装問題。

あるフラクタルのfirst generationのサイズをaとすると、n回generationを繰り返した結果の総線長は

最初の長さ+2回目で追加される長さ+3回目で追加される長さ+...

= a+(1/3*a*2)+(1/9*a*2*3)+(1/27*a*2*9)+... = a+(2/3*a)*(n-1)

rectangleの座標は整数なので、フラクタルが1*1の大きさを超える間は(n<=4)まで再帰的にrectangleに含まれるか計算し、

n>4になるときは上に書いた式で一気に総線長を計算すれば良さそう

書く

バグバグすぎてどうにもならなくなる

時間切れ

後で

何とか直したがこのコードは場合分けが多すぎて煩雑でだめな気がする

もっとスマートな書き方を考えられなければ・・・

ソースコード

class FractalPicture {
public:
	double rec(int x1, int y1, int x2, int y2, int dep, int dir, int rx, int ry) {
		double res=0;
		int len=81;
		for(int i=0; i<dep; i++) len/=3;
		int nrx, nry;
		if(dep<4) len=len*2/3;
		if(dir==0) {
			if(x1<=rx && x2>=rx) {
				if(y1<ry && y2>=ry && y2<=ry+len) res+=y2-ry;
				else if(y1>=ry && y2<=ry+len) res+=y2-y1;
				else if(y1<ry && y2>ry+len) res+=len;
				else if(y1>=ry && y1<=ry+len && y2>ry+len) res+=ry+len-y1;
				if(dep==4 && y1<=ry && y2>=ry+1) {
					if(x2>=rx+1) res+=inc;
					if(x1<=rx-1) res+=inc;
				}
			}
			nrx=rx; nry=ry+len;
		} else if(dir==2) {
			if(x1<=rx && x2>=rx) {
				if(y1<ry-len && y2>=ry-len && y2<=ry) res+=y2-(ry-len);
				else if(y1>=ry-len && y2<=ry) res+=y2-y1;
				else if(y1<ry-len && y2>ry) res+=len;
				else if(y1>=ry-len && y1<=ry && y2>ry) res+=ry-y1;
				if(dep==4 && y1<=ry-1 && y2>=ry) {
					if(x2>=rx+1) res+=inc;
					if(x1<=rx-1) res+=inc;
				}
			}
			nrx=rx; nry=ry-len;
		} else if(dir==1) {
			if(y1<=ry && y2>=ry) {
				if(x1<rx && x2>=rx && x2<=rx+len) res+=x2-rx;
				else if(x1>=rx && x2<=rx+len) res+=x2-x1;
				else if(x1<rx && x2>rx+len) res+=len;
				else if(x1>=rx && x1<=rx+len && x2>rx+len) res+=rx+len-x1;
				if(dep==4 && x1<=rx && x2>=rx+1) {
					if(y2>=ry+1) res+=inc;
					if(y1<=ry-1) res+=inc;
				}
			}
			nrx=rx+len; nry=ry;
		} else if(dir==3) {
			if(y1<=ry && y2>=ry) {
				if(x1<rx-len && x2>=rx-len && x2<=rx) res+=x2-(rx-len);
				else if(x1>=rx-len && x2<=rx) res+=x2-x1;
				else if(x1<rx-len && x2>rx) res+=len;
				else if(x1>=rx-len && x1<=rx && x2>rx) res+=rx-x1;
				if(dep==4 && x1<=rx-1 && x2>=rx) {
					if(y2>=ry+1) res+=inc;
					if(y1<=ry-1) res+=inc;
				}
			}
			nrx=rx-len; nry=ry;
		}
		if(dep==4) {
			return res;
		}
		res+=rec(x1, y1, x2, y2, dep+1, dir, nrx, nry);
		res+=rec(x1, y1, x2, y2, dep+1, (dir+1)%4, nrx, nry);
		res+=rec(x1, y1, x2, y2, dep+1, (dir+3)%4, nrx, nry);
		return res;
	}

	double getLength(int x1, int y1, int x2, int y2) {
		double res;

		inc=((1./3+(2./9*494))*3-1./3)/2;
		res=rec(x1, y1, x2, y2, 0, 0, 0, 0);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110320