問題

難しい和音 | MojaCoder

https://mojacoder.app/users/riantkb/problems/toj_ex_1/

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

考察

• ぱっと見ゼッケンドルフの定理が使えそう

• 後ろから貪欲に取るもののサンプルが合わない

• $\sum_{i=0}^n F_i=F_{n+2}-1$ という等式を発見

• 後ろから枝刈り全探索が通りそう

• AC

何故うまくいくのか

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

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

• $F_{n+2}$ を取った場合: その後のとり方は複数ある

• $F_{n+2}$ を取らなかった場合: 隣あう二連続の値を取ることは考えないのでその後のとり方は一意に定まる

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