No.320

正しいフィボナッチ数を $f_i$ とする.

$a_i = f_i - 1$ とすると, 以後間違えなかったとしたら,

$a_{i+m} = f_{i+m} - f_m$ となり, 誤差はフィボナッチ数列となる.

複数回間違えた場合でも誤差はやはりフィボナッチ数列で積み上がっていくので, $i_1, i_2, i_3, \dots$ 番目に間違えたとすると,

$$a_i = f_i - (f_{i-i_1} + f_{i-i_2} + f_{i-i_3} + \dots)$$

となる. よって,

$$f_N - a_N = f_{N-i_1} + f_{N-i_2} + f_{N-i_3} + \dots$$

となるので, $f_N - a_N$ が $N-2$ 項までの複数の異なる項のフィボナッチ数の和で表せるかどうか, 表せた場合は最小いくつの項の和で表せるかを求める問題となる.

ここで,

$$f_1 + f_2 + \dots + f_{N-2} = f_N - 1$$

となるので, $f_N - a_N \geq f_N$ のときは表せないが, 今回は $a_N \geq 1$ なので考えなくてもいい.

ここで $f_{i+1} < n < f_{i+2}$ となる $n$ が $f_i$ 以下のフィボナッチ数の和で表せるとすると,

$$f_{i+1} - f_{i} < n - f_i < f_{i+2} - f_{i} \\ f_{i-1} < n - f_i < f_{i+1}$$

となるので, $n - f_i$ は $f_{i+1}$ 以下のフィボナッチ数の和で表せる. よって, 貪欲法で大きいフィボナッチ数から引いていけばいい.