読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

天下一プログラマーコンテスト2012 決勝 : A ぶんたん

その他コンテスト

決勝出てないけど、練習で解いてみた。
http://tenka1-2012-final.contest.atcoder.jp/tasks/tenka1_2012_final_a

10^10までの整数値が与えられるので、フィボナッチ数列中の数の和で最小何個あればその数値を求められるか答える。

フィボナッチ数列は F[i+2]=F[i+1]+F[i] なので、F[i+2]を採用できるならした方が良い(F[i+1]とF[i]に分けると必要な数が1個増える)ということで、与えられた数から、数列の大きな方から順に引いていき、引けた数をカウントすればよい。

s64 F[500];


void solve() {
	int f,r,i,N;
	int m=0,nm=0,s=0,c=0;
	s64 v;
	
	F[0]=0;
	F[1]=1;
	for(N=2;N<500;N++){
		F[N]=F[N-1]+F[N-2];
		//_P("(%d:%lld)",N,F[N]);
		if(F[N]>10000000000LL) break;
	}
	
	scanf("%lld",&v);
	i=N-1;
	while(i>0) {
		if(v>=F[i]) {
			v-=F[i];
			c++;
		}
		i--;
	}
	_P("%d\n",c);
	
}

まとめ

なぜ単純に引いていけばいいか、自分でも確証はもててないけど通ったからいいか。

広告を非表示にする