yukicoder No.320 眠れない夜に

問題

No.320 眠れない夜に - yukicoder

解法

フィボナッチ数列の第 n 項を fib[n] とします。

を計算する際に間違えて -1 したとすると, そのマイナスの影響は, 第 m+n 項には fib[n] になって帰ってきます。

なので, やることとしては, 第 N 項の数をフィボナッチ数で減らしていって, M と一致させる, ということをやればいいわけです。この時, M と一致させるために必要な最小の誤り数を求めることです。
最小の誤り数を求めるときは, 大きいフィボナッチ数を優先して数を M に近づけていけば良いです。

ll fib[82];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll M;
    cin >> N >> M;
    N--;
    fib[0] = fib[1] = 1;
    for (int i = 2; i < 80; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    if (fib[N] < M) {
        cout << -1 << endl;
        return 0;
    }
    ll diff = fib[N]-M;
    int ans = 0;
    for (int i = N-2; i >= 0; i--) {
        if (!diff) break;
        if (diff >= fib[i]) {
            ans++;
            diff -= fib[i];
        }
    }
    if (diff) ans = -1;
    cout << ans << endl;
    return 0;
}