yukicoder No.320 眠れない夜に

正しいフィボナッチ数列を $F_i$ とする（indexは $F_3=2$ となるよう取る）
$i\leq0$ に対しては $F_i=0$ とおく（漸化式に従って添字を負に拡張した定義とは異なることに注意）

厳密に証明しようとすると死ぬほどめんどくさいので答えだけ先に行っておくと
「 $M>F_N$ なら-1、さもなくば和が $M-F_N$ になるように $F_i\ \ (i\leq N-2)$ を大きい方から貪欲に取った時の個数」となる

いくつか実験してみると直感的には明らかなのだけど、数学的に厳密に証明しようとすると大仰になってしまった。

＝＝＝証明＝＝＝

計算間違いでは真値より小さくしかならないことから、 $M>F_N$ ならそのような間違え方は存在しない
$M\leq F_N$ とする。

適当な整数 $k\geq3$ をとり、数列 $\{a_i\}$ を
$\begin{eqnarray*} a_1&=&a_2=1&\\ a_i&=&a_{i-1}+a_{i-2}&(i\geq3,i\neq k)\\ a_k&=&a_{k-1}+a_{k-2}-1&\end{eqnarray*}$
で定める（つまりaは第k項の計算を間違え、それ以外は正しく計算した数列）
このとき $i\geq k$ に対し
$\begin{eqnarray*}F_{i+1}-a_{i+1}&=&(F_i+F_{i-1})-(a_i+a_{i-1})\\ \ &=&(F_i-a_i)+(F_{i-1}-a_{i-1})\end{eqnarray*}$
であり
$F_i-a_i=0 \ \ \ \ \ (i< k)$
$F_k-a_k=1$
なので $F_i-a_i=F_{i-k+1}$ となる。

k,m(k＜m)の2回で計算を間違えた場合は、その数列をbとし、aを上と同じく取れば同様の議論により $a_i-b_i=F_{i-m+1}$ となるので
$\begin{eqnarray*}F_i-b_i&=&(F_i-a_i)+(a_i-b_i)\\&=&F_{i-k+i}+F_{i-m+1}\end{eqnarray*}$
となる。
帰納的に、第 $k_j$ 項の計算で間違えた場合、第i項は $F_i-\sum_{j}F_{i-k_j+1}$ 　になる
よって問題は「 $\alpha:=F_N-M$ を $\{F_{N-k+1}|3\leq k\leq N\}=\{F_k|1\leq k\leq N-2\}$ の相異なる元の和として表す事ができるか、できるならそのために必要な元の個数は最小でいくつか？」となる
（仮定より $0\leq\alpha< F_N$ である）
・存在
Nに関する帰納法で示せる。
$N=3$ のとき明らか
$N\geq 4$ のとき、 $\alpha< F_{N-1}$ なら帰納法の仮定より成立。そうでないなら $F_{N-2}$ をとれば $\alpha-F_{N-2}< F_N-F_{N-2}=F_{N-1}$ なので帰納法の仮定から成立。
・最小性
大きい方から貪欲にとった時に個数が最小になることを示す
$\alpha\geq F_k$ なる最大のkを取る。（仮定より $0\leq k\leq N-1$ ）
ゲース1： $k=N-1$ のとき
$\sum_{i=1}^{N-3}F_i=F_{N-1}-1<\alpha$ なので*1必ず $F_{N-2}$ を使う
ケース2： $k< N-1$ のとき
$\alpha=F_k$ のとき明らか。 $\alpha>F_k$ とする
αを、 $F_k$ を使わずに $F_1 ... F_{k-1}$ の相異なるものの和で表すのが最小であると仮定する
このとき、 $\sum_i F_{k-1-2i}\leq F_k<\alpha$ なので*2、そのような組み合わせは必ず隣接する2項を含む
そのなかで最大のものを $F_{x-2},F_{x-1}$ であるとすると、xの取り方から $F_x$ は使われていないので、この2項を $F_x$ に取る変えることができる。
仮定より $x\leq k\leq N-2$ なので取り替えた後の組み合わせも条件を満たし、最小性に反する。

＝＝＝証明終＝＝＝

（余談）
解説で触れられているゼッケンドルフの定理 - Wikipediaは多分あんまり関係ないと思う。これは「任意の数は隣接しないフィボナッチ数の和として一意に表せる」であり、今回の問題に対応しそうな形に書きなおせば「 $\alpha$ は $F_i\ \ (i\leq N-1)$ の隣接しない～～」であり、 $F_{N-1}$ も使える点が大きく異る。これを使わないようにするには、例えば「 $F_{N-1}$ があれば $F_{N-2}+F_{N-3}$ にバラす」などの方法があるが、元の表現に $F_{N-3}$ が含まれていた時には～～などと考えると、結局は帰納法で示すしか無く、だったら別にゼッケンドルフの定理使わなくても…という感じ。
（余談終わり）

$F_{80}=23416728348467685\fallingdotseq 2.3*10^{16}$ なのでフィボナッチ数列の計算は64bitで大丈夫

int main(){
	long m,f[90];
	int n,i,c=0;
	f[1]=f[2]=1;
	for(i=3;i<=80;i++)f[i]=f[i-1]+f[i-2];
	scanf("%d%ld",&n,&m);
	m=f[n]-m;
	if(m<0){puts("-1");return 0;}
	for(i=n-2;m;i--)if(m>=f[i]){m-=f[i];c++;}
	printf("%d",c);
	return 0;
}

ささっと縮めて

long m,f[99];
s;
main(n){
	for(f[1]=1;++n<90;f[n]=f[n-1]+f[n-2]);
	scanf("%d%ld",&n,&m);
	for(m=f[n--]-m;--n;m/f[n]?m-=f[n],s++:0);
	s=!printf("%d",m?-1:s);
}

f[1]=1っていうのが邪魔っぽいので頑張って睨むと

for(f[1]=1;++n<90;f[n]=f[n-1]+f[n-2]);
for(;--n+90;f[1-n]=f[-n]+f[~n]+!n);

とできるので（f[-1]を読んでいる）

long m,f[99];
s;
main(n){
	for(;--n+90;f[1-n]=f[-n]+f[~n]+!n);
	scanf("%d%ld",&n,&m);
	for(m=f[n--]-m;--n;m/f[n]?m-=f[n],s++:0);
	s=!printf("%d",m?-1:s);
}

144B

*1:フィボナッチ数 - Wikipedia

*2:同上

メモ

yukicoderでゆるふわgolf

yukicoder No.320 眠れない夜に