yukicoder No.320 眠れない夜に - アルゴリズマーの備忘録

今年最後の問題かなぁ…（冬休みの課題の息抜きに）

問題

解法

まず、早めに間違えると大きな誤差を生むことが分かる。その様子を見てみる。例えばa3で間違えると、
a3=1(-1)、a4=2(-1)、a5=3(-2)、a6=5(-3)、…
と、元の値からどの位離れていくかがフィボナッチ数列になる。

よって、予めフィボナッチ数列の80項まで調べておき（ギリギリC++のlong longで収まる。不安だったのでJavaでBigInteger使って確かめた。）、どの位足りないかを見るためm=an-mとする。
a3に間違えた時から順に仮定していき、変化量がm以下ならmから引いてあげる。実際はフィボナッチ数列のa(n-2)から値を下げるようループを回してあげる。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fib[100];
bool use[100];
int main(){
    fib[0]=fib[1]=1;
    for(int i=2;i<80;i++)   fib[i]=fib[i-1]+fib[i-2];
    ll n,m; cin>>n>>m;  m=fib[n-1]-m;
    int ans=0;
    for(int i=n-3;i>=0;i--){
        if(not(use[i]) and m>=fib[i]){
            m-=fib[i];
            ans++;
            use[i]=true;
        }
    }
    if(m==0) cout<<ans<<endl;
    else  cout<<-1<<endl;
    return 0;
}

感想

いや、普通にJava使えば良かったのでは…Javaの練習問題にも丁度いい気がする。
来年はPythonとJavaをさっさと使えるようにしましょう。