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

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.320 眠れない夜に

問題はこちら
No.320 眠れない夜に - yukicoder

正しいフィボナッチ数列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は多分あんまり関係ないと思う。これは「任意の数は隣接しないフィボナッチ数の和として一意に表せる」であり、今回の問題に対応しそうな形に書きなおせば「\alphaF_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