SRM512 Div1 Medium(512) SubFibonacci

SubFibonacci

整数2個とその整数の間隔を決めれば、フィボナッチ数列が一意に定まる。ある数より大きな数のみのフィボナッチ数列の最長部分列の長さを覚えておけば良い。

#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

vector<int> S;
const int M = 100000000;
vector<int> F;

map<int,int> memo[2];

int pick( int depth, int lower )
{
    if ( depth >= 2 )
        return 0;
    if ( memo[depth].count(lower) )
        return memo[depth][lower];

    int n = (int)S.size();
    int ans = 0;

    //  1個だけ取る
    for ( int i=0; i<n; i++ )
    if ( lower < S[i] )
        ans = max( ans, pick(depth+1,S[i])+1 );

    //  2個以上取る
    for ( int i=0; i<n; i++ )
    if ( lower < S[i] )
    for ( int j=i+1; j<n; j++ )
    for ( int d=1; d<(int)F.size(); d++ )   //  選んだ2個の間隔
    {
        int x=S[i], y=S[j];

        //  xの前の項
        int z = (int)((y-(long long)F[d]*x)/F[d-1]);

        if ( y == F[d]*x+F[d-1]*z &&
             x+z > 0  &&    //  フィボナッチ数列は正整数のみ
             z != 0 )       //  a a 2a 3a　のような数列はz=x=aで捕らえる
        {
            int num = 0;
            int a = z;
            int b = x;
            while ( b<=S.back() )
            {
                if ( b >= x  && 
                     binary_search(S.begin(),S.end(),b) )
                {
                    num++;
                    ans = max( ans, pick(depth+1,b)+num );
                }
                int c = b+a;
                a = b;
                b = c;
            }
        }
    }
    
    return memo[depth][lower] = ans;
}

class SubFibonacci{public:
int maxElements( vector <int> S )
{
    ::S = S;
    sort(::S.begin(),::S.end());

    F.clear();
    F.push_back(1);
    F.push_back(1);
    for ( int i=2; F.back()<=M; i++ )
        F.push_back(F[i-2]+F[i-1]);

    memo[0].clear();
    memo[1].clear();

    return pick( 0, 0 );
}};