天下一プログラマーコンテスト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]に分けると必要な数が１個増える)ということで、与えられた数から、数列の大きな方から順に引いていき、引けた数をカウントすればよい。

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

まとめ

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