SRM524 Div1 Medium(500) LongestSequence

TopCoder

LongestSequence

Cの要素数が2の場合が↓に載っていた。数列の長さが絶対値の和を超えることは無いらしい。

Solution for October 2008 - Math Central

長さnの数列vを考える。Si = Σj=0i-1v[i]とすると、長さkの全ての連続した部分列の和が正であることと、Si<Si+kが全てのiについて成り立つことは同値。Sの大小関係が決まるので、それをグラフの有向辺として、グラフが閉路を持たなければそのような数列Sが作れる。閉路があればSは作れない。順番に調べていっても間に合ったけど、二分探索の方が安全。

#include <vector>
using namespace std;

bool visit( vector<vector<int> > &e, int v, vector<int> &c )
{
    c[v] = 1;
    for ( int i=0; i<(int)e[v].size(); i++ )
    {
        if ( c[e[v][i]]==2 )  continue;
        if ( c[e[v][i]]==1 )  return false;
        if ( ! visit(e,e[v][i],c) )  return false;
    }
    c[v] = 2;
    return true;
}

bool topological_sort( vector<vector<int> > &e )
{
    int n = (int)e.size();
    vector<int> c(n);
    for ( int i=0; i<n; i++ )
    if ( c[i]==0 )
        if ( ! visit(e,i,c) )
            return false;
    return true;
}

class LongestSequence{public:
int maxLength( vector <int> C )
{
    int n = (int)C.size();

    int l = 0;
    int r = 10000;

    while ( r-l >= 2 )
    {
        int m = (l+r)/2;

        vector<vector<int> > v(m+1);
        for ( int i=0; i<=m; i++ )
            for ( int j=0; j<n; j++ )
                if ( 0<=i+C[j] && i+C[j]<=m )
                    v[i].push_back(i+C[j]);

        if ( topological_sort( v ) )
            l = m;
        else
            r = m;
    }

    return l<9999 ? l : -1;
}};