フィボナッチ数列（★3 Edition）（★★★）

2 secs 1024 MB

解説

数学的な問題文でかなり難しそうに見えますが、定義の通りに実装しましょう。

例えば、以下の実装方針が考えられます。

問題文の関数を再帰関数で実装すると、以下の通りになります。

def フィボナッチ(i) {
    if (1 <= i <= N) {
        return A[i]
    } else {
        return フィボナッチ(i - 1) + ... + フィボナッチ(i - N)
    }
}

しかし、これだとフィボナッチ関数の計算回数が爆発的に増加してしまいます。（時間計算量 $O(N \cdot2^M)$ ）

そこで、関数の返り値をメモしておき、再度呼ばれたときはその値を即時に返すことで、非効率的な再計算をする必要がなくなります。

これで、 $O(NM)$ となり、 $T$ 個のテストケースを実行しても十分間に合います。