pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Manthan, Codefest 16 D. Fibonacci-ish

codeforces.com

解法

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|)) は怖い。