Codeforces Manthan, Codefest 16 D. Fibonacci-ish
解法
f0, f1 を O(n2) で総当りする。
f0=f1=0 でなければ fn は指数オーダーで増加するので実際にシミュレートしても大して時間はかからない。 f0=f1=0 のときはシミュレートすると全て 0 のケースで非常に時間が掛かってしまうので注意。
最悪ケースは大量の 1 とフィボナッチ数列を組み合わせたもの。
1 1 1 1 1 1 ... 1 2 3 5 8 13 21 ...
すでに計算した初項の組は再計算しない、あるいは map の使用回数を抑える等の工夫をしないと TLE する。
Codeforces Manthan, Codefest 16 D. Fibonacci-ish
n=1000 で O(n^2 log^2 max(|a|)) は怖い。