難しい和音【Mojacoder】解説 - hotmanの備忘録とライブラリ置き場

問題

初項がA,Bのフィボナッチ数列の部分和として正整数Mを表す時、部分和の要素数の最大値を求める問題

$\sum_{i=0}^n F_i=F_{n+2}-1$ より、 $F_{n+2}$ が取れる状況で $F_{n+2}$ または $F_{n+1}$ を取らない事は出来ない

また、map等で管理することにより、隣あう二連続の値を取る場合は考えないで良い(隣り合わないとり方で同じ数字を表せるため)

よって最大 $\mathcal{O}(\log M)$ 個の分岐しか存在しないことが分かるので全体で $\mathcal{O}(\log ^2 M)$ で解ける