Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-07SRM475 Div1

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