yukicoder : No.320 眠れない夜に

以前yukicoderでフィボナッチ数列の問題出す際に色々考えただけあって、すんなり解けた。
http://yukicoder.me/problems/875

問題

以下のように構成される数列Aを考える。このAはフィボナッチ数列である。

• A[1]=1
• A[2]=1
• A[i]=A[i-1]+A[i-2] (i≧3)

ただこの式でA[3]以降を順次計算する際、一部のiでA[i]=A[i-1]+A[i-2]-1と1小さく数えてしまった。
こうして数えた数列のA[N]がMであったとき、どのiで計算を間違えたか最小回数を求めよ。

解法

ミス無しで数えた正しいフィボナッチ数列をB[i]とする。
多く数え間違えることはないので、M＞B[N]の時は解無し。
A[i]で1小さく数え間違えると、A[i+1]は1、A[i+2]は2、A[i+3]は3、A[i+4]は5…と結局A[i+k]はB[i+k]よりB[k+1]だけ小さくなることがわかる。
よって、A[3],A[4],A[5], ..., A[N]で間違えることは、それぞれA[N]をB[N]からA[N-2], A[N-3], A[N-4], ...A[1]だけ小さくしてしまうに等しい。

よって、A[1]～A[N-2]の和でB[N]-Mの値を構成できれば、それが解となる。
これは貪欲に解くことができ、j=N-2から降順に、「あと埋めなければいけない差がB[j]以上あれば、B[j]引く(A[N+1-j]の計算で1間違えたことにする)」を差が0になるまで繰り返せばよい。

int N;
ll M;
ll A[100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	A[1]=1;
	for(i=2;i<=90;i++) A[i]=A[i-1]+A[i-2];
	
	int num=0;
	ll diff=A[N]-M;
	for(i=3;i<=N;i++) {
		ll v=A[N-i+1];
		if(v<=diff) diff -= v, num++;
	}
	
	if(diff) return _P("-1\n");
	_P("%d\n",num);
	
}

まとめ

良くわからんという方はフィボナッチ数列の理解を進めるために↓を解きましょう。
No.195 フィボナッチ数列の理解(2) - yukicoder