Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-07SRM475 Div1

SRM475 Div1 300 RabbitStepping

| 23:22 | SRM475 Div1 300 RabbitStepping - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM475 Div1 300 RabbitStepping - SRM diary(Sigmar) SRM475 Div1 300 RabbitStepping - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→シミュレーションか

→計算量は高々17_C_8=24300回のシミュレーション。2^17でも128000だから余裕そう。

→何らかの法則性がありそうな問題の気もするが・・前の失敗もあるから、ナイーブに実装することにしよう。

→書く→サンプル合わない

→ミスだらけ・・問題の読み違い、条件分岐の間違い、For文終了条件の間違い、etc...

→ちょっと酷すぎました。もっと集中力を高めて書くときのミスを減らさなければ・・

→サンプル通る(結局30分もかかりました・・)

→コードが汚すぎてプログラム上のミスを確認する気にもなれない。コーナーケースを確認して提出。

→500へ


チャレンジフェーズ

→みんなシミュレーションのコードが長いから確認が大変すぎる・・

→この問題はサンプル通ってれば問題ないような気がするけど・・・

→特になにもせず


システムテスト

→Passed


以下、ソースです。

最初、Redのマスのために元の位置を各ウサギ毎に記憶する必要があると思ってしまいましたが、よく考えると同じマスに重なったウサギは消滅するので、ウサギ毎ではなくマス毎に状態を記憶すれば良かった。そうすればもう少し早く書けたかな。。。

class RabbitStepping {
public:
	string f;
	int N;
	ll cnt(int mask, int r) {
		ll res=0;
		int rabit[17], nxt[17], num[17], del[17];
		
		int c=0;
		for(int i=0; i<N; i++) {
			if(mask&(1<<i)) {
				rabit[c]=i;
				if(f[i]=='R') nxt[c]=-1;
				c++;
			}
		}
		for(int j=N; j>2; j--) {
			memset(num, 0, sizeof(num));
			for(int i=0; i<r; i++) {
				if(rabit[i]<0) continue;
				if(rabit[i]==0 || (rabit[i]<j-2 && f[rabit[i]]=='B')) {
					rabit[i]++;
					nxt[i]=-1;
				} else if(rabit[i]>=j-2 || f[rabit[i]]=='W') {
					rabit[i]--;
					nxt[i]=1;
				} else if(f[rabit[i]]=='R') {
					rabit[i]+=nxt[i];
					nxt[i]=-nxt[i];
				}
				num[rabit[i]]++;
			}
			memset(del, 0, sizeof(del));
			for(int i=0; i<r; i++) {
				if(rabit[i]<0) continue;
				if(num[rabit[i]]>1) del[i]=1;
			}
			for(int i=0; i<r; i++) {
				if(del[i]) rabit[i]=-1;
			}
		}
		for(int i=0; i<r; i++) {
			if(rabit[i]>=0) res++;
		}
		return res;
	}
	double getExpected(string field, int r) {
		double res;
		ll deno=0, nume=0;
		N=field.size();

		f=field;

		for(int i=1; i<(1<<N); i++) {
			if(__builtin_popcount(i)!=r) continue;
			nume+=cnt(i, r);
			deno++;
		}
		res=(double)nume/deno;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100707