結果

問題 No.320 眠れない夜に
ユーザー n_vipn_vip
提出日時 2015-12-13 10:59:42
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 1,368 bytes
コンパイル時間 115 ms
コンパイル使用メモリ 5,336 KB
実行使用メモリ 4,480 KB
最終ジャッジ日時 2023-10-13 14:49:19
合計ジャッジ時間 1,341 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
権限があれば一括ダウンロードができます

ソースコード

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