天下一プログラマーコンテスト2012 決勝 A - ぶんたん

本番中は「貪欲でいけるんじゃね？　間違えたところでペナルティは5分だし、試してみようw」と貪欲で書いた。

実はこれが正しくて、貪欲に大きいフィボナッチ数を引いていくだけで、答えが得られる。

証明。k番目のフィボナッチ数をF_kとする。①Nを最小個数のフィボナッチ数の和で表したならば、その中に連続したフィボナッチ数は含まれない。F_kとF_k+1が含まれていたら、それらを取り除いて、F_k+2を加えることができるので。②Nをフィボナッチ数の和で表したとき、同じフィボナッチ数F_kが2個含まれていたら、同数の相異なるフィボナッチ数の和で表せる。なぜなら、2F_k=F_k+F_k-1+F_k-2=F_k+1+F_k-2。①②の操作では、常に、より大きなフィボナッチ数を加えているので、この操作は必ず終わる。よって、任意の自然数は、フィボナッチ数の個数が最小となるように、連続しない相異なるフィボナッチ数の和で表せる。Zeckendorf's theoremにより、自然数を連続しない相異なるフィボナッチ数で表す方法は一意であり、貪欲に大きなフィボナッチ数を引いていくことで得られる。

N = input()
F = [1,2]
while F[-1]<N:
    F += [F[-1]+F[-2]]
c = 0
for f in F[::-1]:
    if f<=N:
        N -= f
        c += 1
print c