Codeforces #213, Division 2, B : The Fibonacci Segment

問題文

http://codeforces.com/contest/365/problem/B

概要

数列 a が与えられる。
この列の連続する部分列であって、次の制約を満たすものの内で最長のものの長さを求めよ

• 有効な i, i - 1, i - 2 について、

解法

先頭と末尾を全て試すと間に合いません。

ある始点 i を決めたとき、最長の列の末尾のインデックスが j だとします。
このとき、j で終わる解候補は i で始まるものが最長となります。
従って、次に試すべき始点は j になります。
このようにして試す始点を減らすと全体では線形時間になるので間に合います。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int res = min( 2, n );
	REP( i, 0, n )
	{
		int j;
		for ( j = i + 2; j < n && as[j] == as[ j - 1 ] + as[ j - 2 ]; j++ );
		res = max( res, min( n, j - i ) );
		i = j - 2;
	}

	cout << res << endl;

	return 0;
}