TopCoder SRM 524 Div1 Medium LongestSequence

この解法は自力じゃ思い浮かばんわ…。
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;
		
	}
};

まとめ

こんなグラフ化は思いつかないわ…。
実際今回正答者少なかったしね。