結果

問題 No.320 眠れない夜に
コンテスト
ユーザー n_vip
提出日時 2015-12-13 10:59:42
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 1,368 bytes
コンパイル時間 61 ms
コンパイル使用メモリ 5,120 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 11:34:33
合計ジャッジ時間 1,019 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

こうすると証明できそうです。

F_i=a_1+...+a_i (フィボナッチ数列のi項目までの和)
と置きます。このとき、

(1) 1,...,F_iは全部i項目までの部分和で表せる
(2) そのような表し方で足し算の回数が最小となるのはでかい方から貪欲に使った場合である
を帰納法で示します。
i==1のときは明らかです。

j<iである任意のjで(1),(2)が成り立ってると仮定して、iでも成り立つことを示します。

(1)
x <= F_iであるxを表したいとする。 
x < a_i なら、当然 x<=F_{i-1} だから帰納法の仮定が使えてOK
x >= a_iなら、 x <= F_i より、 x-a_i <= F{i-1} となって、x-a_iに帰納法の仮定が使えて、
x = （i-1項目までの部分和） + a_i
と表せるからOK

(2)
x > F_{i-1}だったら当然a_iを使わなきゃいけない。
そうでなくても、a_i <= x であるxを表すときには、絶対a_iを使ったほうがお得であることを示す。
a_i を使わない時、 a_{i-1}まででxを表す事になる。このとき、帰納法の仮定より貪欲に使っていくことになるが、x >= a_i = a_{i-1} + a_{i-2}なので、
x =  a_{i-1} + a_{i-2} + （何か）
という形をしているはずである。どう考えても
x =  a_i + （何か）
とした方がお得である。
0