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

SRM475 Div1 600 RabbitIncreasing

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

Problem Statement

問題を見る

→えーと・・問題文が無駄にややこしいです・・・何月にどうなるとか、分かりにくいです

→つまりこれは漸化式にするのかな?

→生まれて1年目、2年目、3年目以降に分けると漸化式にできますね

→kが大きいようだから行列にして計算する問題なのかな

→時間がないし早く書こう

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

→うーん・・・あ・・MODだから普通に減算したり2で割ったらダメだ・・

→というか、ここが難しいところか。あせりすぎた・・

→時間切れ


チャレンジフェーズ

→2人しか提出してない。

→うーむ・・そうか、実はkは1000万しかなかったからO(N)で良かったのか・・ちゃんと問題を読んでなかったな・・・何となく10億くらいと勝手に思ってた

→1人はどう見てもオーバーフローしているので怪しげなコードだけど落とせるのか良くわからない。赤の人だし罠か・・

→結局何もせず終了


終了後

→とりあえずMODの中で2で割るところは、2^(MOD-2)をかけるように変更

→でも、3年目ウサギの数が全体の半分より多いか等の判断はどうするのか・・

→うーん・・ああ、year=1以外の場合は必ず1年目ウサギと3年目ウサギの数が等しいのか。ということは、3年目ウサギを0にして、2年目ウサギを半分にすれば良い。

→2年目ウサギの偶奇で計算方法が変わるがここはどうするのか・・・

→MOD2で並行して2年目ウサギの数を計算してみよう

→ダメだ、1度2で割ると偶奇が分からなくなる

→ということは、MOD4でやれば・・

→やはりダメか、2度2で割ると偶奇が分からなくなる・・

→ん・・?じゃあ最大50回しか2で割らないから、MOD2^50でやれば・・

→何となくいけそうな気がする

→サンプル通る

→Passed System Test


以下、終了後にシステムテストを通したソースです。

色々試してみましたが、やはりMOD2^50なら通るけど、MOD2^49だと通りませんので考え方は合ってると思います。

typedef long long ll;
const int MOD=1000000009;

ll powgf(ll a, ll e, ll m) {
	ll res=1;
	for(; e; a=(a*a)%m, e>>=1) {
		if(e&1) res=(res*a)%m;
	}
	return res;
}
ll divgf(ll a, ll b, ll m) { return (a*powgf(b, m-2, m))%m; }

class RabbitIncreasing {
public:
	int getNumber(vector <int> leaving, int k) {
		ll res;
		ll x=0, y=0, z=1;//x:3年目以降ウサギ、y:2年目ウサギ、z:1年目ウサギ
		ll x2=0, y2=0, z2=1;//MOD 2^50での演算用変数
		ll MOD2=(1LL<<50);

		if(leaving[0]==1) return 0;
		int j=0;
		for(int i=2; i<=k; i++) {
			x=(x+y)%MOD;
			y=z;
			z=x;
			x2=(x2+y2)%MOD2;
			y2=z2;
			z2=x2;
			if(j<leaving.size()) {
				if(i==leaving[j]) {
					x=0;
					x2=0;
					if(y2&1) {
						y--;
						y2--;
					}
					y=divgf(y, 2, MOD);//y*(2^(MOD-2))
					y2/=2;
					j++;
				}
			}
		}
		res=(x+y+z)%MOD;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100707