Yuki 320 眠れない夜に ( Math, Fibonacci )

No.320 眠れない夜に - yukicoder

かなりフィボナッチ数列の勉強になったので、ちょっとノートをします。pekempey さんの記事を参考にしました。

ある項目に 1 少なく数えるのは、その項目から と負のフィボナッチ数列を並列して進ませる事と同じで、縦の総和が結果の数になる。解説にわかりやすいイメージがあるので、ちょっと借ります。

つまり、 をフィボナッチ数列中の数の総和で表したい。その上使う数を最少化したい。
その存在性はゼッケンドルフの定理 にあるように再帰的に示せる。

使う数を最少化するために、これらを知っておきたい：



証明は難しくないですが、リンクを載せます。

として、式 1 から に導く。か のうち一つは使わなければいけない事がわかる。次に、式 2 と 3 と「連続するフィボナッチ数は使わない事」から、同じく上限を見積もってみると を使う事が常に最善だという事がわかる。

この貪欲法で大体行けばいいのですが、「1 回目と 2 回目は決して間違わない」から、と を使ってはいけない事になるが、 の場合の答えは直接 0、の場合 -1 とすれば、残りのケースは なので全部辻褄が合う。

int N;
ll M;

void init(){
  cin >> N >> M;
}

vl fib;

void preprocess(){
  fib = vl( 80 + 1 );
  fib[ 1 ] = fib[ 2 ] = 1;
  for( int i = 3; i <= 80; ++i )
    fib[ i ] = fib[ i - 1 ] + fib[ i - 2 ];
  if( fib[ N ] < M )
    cout << -1 << endl, exit( 0 );
}

void solve(){
  ll diff = fib[ N ] - M;
  int ans = 0;
  int k = 1;
  while( fib[ k - 1 ] + fib[ k ] <= diff )
    ++k;
  k = min( k, N - 2 );
  while( diff ){
    ++ans;
    diff -= fib[ k-- ];
    while( fib[ k ] > diff )
      --k;
  }
  cout << ans << endl;
}