この解法は自力じゃ思い浮かばんわ…。
http://community.topcoder.com/stat?c=problem_statement&pm=11580
問題
数列C[i]が与えられるので、ここから数列D[i]を作ることを考える。
数列D[i]は以下の条件を満たさなければならない。
- C[i]に正の成分があるなら、D[i]の連続するC[i]要素の和は正である。
- C[i]に負の成分があるなら、D[i]の連続する-C[i]要素の和は負である。
条件を満たすDの最大要素数を答えよ。
解法
最大要素数を仮置きして、二分探索で絞っていく。
Dの累積和S[i]=S[i-1]+D[i]を考える。
すると条件より、以下の大小関係が成り立つ。
- C[i]> 0に対しS[j+C[i]] > S[j]
- C[i]< 0に対しS[j-C[i]] < S[j]
この不等号が矛盾がないことを示せばよい。
すなわちS[i]同士を大小関係に基づいた有向辺を張り、ループがないことをDFSで求めればよい。
なお、C[i]の絶対値の倍以上の要素数でもループがない場合、無限の要素数でもループがないので、それは事前に確認しておく。
class LongestSequence { public: vector<int> C; int okok(int po) { int vis[3000],i; ZERO(vis); queue<int> Q; vis[0]=1; Q.push(0); while(!Q.empty()) { int k=Q.front(); Q.pop(); FOR(i,C.size()) { int tar=k+C[i]; if(tar==0) return 0; if(tar>0 && tar<=po && vis[tar]==0) vis[tar]=1, Q.push(tar); } } return 1; } int maxLength(vector <int> C) { int i; this->C=C; if(okok(3000)) return -1; if(okok(1)==0) return 0; int L=0,R=2048; FOR(i,20) { int po=(L+R)/2; if(okok(po)) L=po; else R=po; } if(okok(L+1)) L++; return L; } };
まとめ
こんなグラフ化は思いつかないわ…。
実際今回正答者少なかったしね。