SRM687 div.1 250 AlmostFibonacciKnapsack

本番は参加できなかったので、ラボのプロコン*1で解いたけど、0完だった

問題

A[1]=2, A[2]=3, A[i+2]=A[i+1]+A[i]-1 となる数列を考える。このとき、あるxが数列Aの異なる要素の和で構成することができるか？
できる場合は、使った要素のインデックスを答えよ。

制約

xは2以上10^18以下

解法

A[i]は、10^18以下のものを列挙しても、100個以下なので、列挙しておく。
2以上の数を順番に計算してみる。
そうすると、図のような3パターンがありそうだということが見えてくる。

A[i] <= x < A[i]について、
パターン(i). x=A[i]のとき→A[i]のみを使う
パターン(ii). x=A[i]+1のとき→A[i-1]とA[i-2]を使う
パターン(iii). x=A[i]+αのとき→A[i]を使って、αをA[1]からA[i-2]で適当に作る
これが正しいことは、数学的帰納法で証明できる。

よってxに対して、以下を繰り返せばよいことがわかる(xが0になったら終了)
(a) x 以下の最大のA[i]を見つける
(b) xとA[i]の差が1のときは、x-=A[i-1]としてi-1を答えに加え、それ以外はx-=A[i]としてiを答えに加える。

計算量

Nをx以下のA[i]の要素の個数とすると、x以下の最大のA[i]を見つけるために二分探索を用いるとO(NlogN)

コード

0-indexになっていることに注意

感想

貪欲でダメだったので、ビットをうまく立てる、みたいなことを考えてたけど解けなかった
1が作れない、みたいなことに気がつければ解けた？(今回は適当な数字ばかり例に出して考えていたけど、小さい方から順に試してみる方法は、確実に頭に入れておく必要がある(これはコーナーケースの注意にもなるので))

*1:今回は2人だけだった。少ない...