Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-10-09SRM484 Div1

SRM484 Div1 250 RabbitNumber

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

Problem Statement

問題を見る

→TaroとHanako・・・出た・・・

→全然分からないし・・・

→まあでも10億なら最悪データ埋め込みで解けそうだな。250でその解はないだろうが・・・

→とりあえず考えてみよう

→えーと・・・1000000000を除くと最大9桁の入力なので、、S(x*x)はたかだか9*18桁=162か

→えーと平方数だから最大144・・・

→18桁で足しあわせて144になる数を列挙すると・・・何かすごく多そう・・ダメぽい(←この辺勘違いしすぎでした。9桁で考え

る問題だったのに・・・。もっとちゃんと考えれば良かった)

→・・・

→an*10^n+...+a0*10^0みたいに分解して考えてみよう

→えーと二乗して展開すると・・・係数は・・・

→いかん、訳わからん。250でこんな複雑なはずがない。やめよう。(←もう少し考えれば良かった・・・)

→・・・

→駄目だ・・全然思いつかない。最終手段で行くか・・

→埋め込み用計算開始

→(計算の間500の問題を読む)

→15分後

→計算終わった→サンプル合わない

→ええええええ

→なんでやねん・・・

→あー・・またintがオーバーフローとかか・・→long longに修正して再度計算

→(500の問題を考える)

→15分後

→そろそろ終わったかな

→あれ・・25%しか進んでない

→そういえばPCがすごく重いぞ

→PCが火傷しそうなほど熱い。やばい。冷やそう

→15分後

→85%程度まで計算した状態で時間切れ・・・終わった・・・


チャレンジフェーズ

→lowからhighまでイテレートしてる人は・・・いない

→intのオーバフローは・・・1人いた。撃墜。+50

→終了


終了後

→あー・・よく考えたら入力は9桁で足しあわせて12以下の数なのか

→そうすると、、21C9で30万くらいしかないから余裕なのか(実際には1桁は9以下なのでもう少し少ない)

→というか、18桁で144になる数って10億より多いし、枝刈りしてるのに元より大きくなるとかありえないし勘違い酷すぎ

→埋め込みに頼りすぎだな。。。ちゃんと考えないと


以下、ソースです。

埋め込み版と枝刈り版です。

枝刈りは足し合わせて9*桁数以下という考えに基づいているので12以下列挙より更に枝刈りしたものになってます(あまり意味は

ないですが・・)


埋め込み版

class RabbitNumber {
public:
	ll calcr(ll n) {
		int res=0;
		while(n) {
			res+=n%10;
			n/=10;
		}
		return res;
	}

	int theCount(int low, int high) {
		int res=0;
		int pre[1050]={/*埋め込みデータは長いので省略*/};

		low--;
		int lb=low/1000000;
		int ls=pre[lb];
		for(int i=1; lb*1000000+i<=low; i++) {
			ll ii=lb*1000000+i;
			ll ri=calcr(ii);
			ll rii=calcr(ii*ii);
			if(ri*ri==rii) ls++;
		}

		int hb=high/1000000;
		int hs=pre[hb];
		for(int i=1; hb*1000000+i<=high; i++) {
			ll ii=hb*1000000+i;
			ll ri=calcr(ii);
			ll rii=calcr(ii*ii);
			if(ri*ri==rii) hs++;
		}

		res=hs-ls;

		return res;
	}
};

枝刈り版

static const double EPS = 1e-7;

class RabbitNumber {
public:
	ll calcr(ll n) {
		int res=0;
		while(n) {
			res+=n%10;
			n/=10;
		}
		return res;
	}

	int theCount(int low, int high) {
		int res=0;

		int sum=0;
		int dig=1;
		int thr=(int)(sqrt(dig*2.*9)+EPS);
		for(ll i=1; i<=high; i++) {
			sum=0;
			ll t=i;
			while(t) {
				sum+=t%10;
				t/=10;
			}
			while(sum>thr) {
				ll t=i;
				ll inc=10;
				while(t) {
					if(t%10) break;
					t/=10;
					inc*=10;
				}
				i+=inc-i%inc;
				sum=0;
				t=i;
				dig=0;
				while(t) {
					sum+=t%10;
					t/=10;
					dig++;
				}
				thr=(int)(sqrt(dig*2.*9)+EPS);
			}
			if(i<low) continue;
			if(i>high) break;
			ll r=calcr(i);
			ll r2=calcr(i*i);
			if(r*r==r2) {
				res++;
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101009