SRM 524 Div1 500 LongestSequence

問題

数列C[i]が与えられる。
C[i]の各項について、

• C[i]が正なら、連続する任意のC[i]項が正
• C[i]が負なら、連続する任意の-C[i]項が負

という制約をつける。
この制約を全て満たす数列のうち、長さが最大のものを答えよ。

無限に長い数列が作れる場合、-1を、
数列が作れない場合は0を返せ。

制約条件

• 1000≦C[i]≦1000

Cの項数≦50

方針

S[i]=a[1]+a[2]+…+a[i]とする。
すると、a[i-k+1]からa[i]までの連続するk項の和が正⇔S[i-k]＜S[i]が成り立つことがわかる。
負の場合は逆にS[i-k]＞S[i]である。

ここで、Sの大小関係をグラフにする。
すなわち、小さいほうから大きい方に辺を貼ったグラフを考える。
これが閉路を持たないことが、条件を満たすS[i]が存在することに他ならない。

ソースコード

vector<vi> g;
int v[500];
bool dfs(int c){
  v[c]=-1;
  rep(i,g[c].size()){
    if(v[g[c][i]]==-1)return 0;
    if(!v[g[c][i]]&&!dfs(g[c][i]))return 0;
  }
  v[c]=1;
  return 1;
}
bool ok(int n,vi &c){
  int m=c.size();
  g=vector<vi>(n+1);
  memset(v,0,sizeof(v));

  rep(i,m)for(int j=0;j+abs(c[i])<=n;j++){
    if(c[i]>0)g[j].pb(j+c[i]);
    else g[j-c[i]].pb(j);
  }
  rep(i,n+1)if(!v[i]&&!dfs(i))return 0;
  return 1;
}
class LongestSequence {
  public:
  int maxLength(vector<int> C)
  {
    int lo=-1,hi=5000,mid;
    while(lo+1<hi){
      mid=(lo+hi)/2;
      if(ok(mid,C))lo=mid;
      else hi=mid;
    }
    if(lo==-1)return 0;
    if(hi==5000)return -1;
    return lo;
  }
};