TopCoder SRM 762 : Div1 Easy LexicographicPartition

問題不足してるのかな？
https://community.topcoder.com/stat?c=problem_statement&pm=15597&rd=17608

問題

整数列が与えられる。
この数列を複数の部分列の連結として分割することを考える。
その際、各部分列の総和が正であるようにしたい。

分割時の部分列の長さならなる数列のうち、辞書順最小のものを求めよ。

解法

数列を繰り返し二分割することを考える。
分割したときの前半と後半がいずれも総和が正となるようにしよう。
その際、長さの列が辞書順最小ということで、前半が条件を満たす最短となるようにしたい。

これは数列の累積和を求めておけば、各分割位置に対しO(1)で判定できる。
後は残された後半を、同様に繰り返し二分割して以降。

ll S[202020];
class LexicographicPartition {
	public:
	vector <int> positiveSum(int n, vector <int> Aprefix, int seed, int Arange) {
		int i;
		ll state=seed;
		while(Aprefix.size()<n) {
			state = (1103515245 * state + 12345);
			Aprefix.push_back(state%(2*Arange+1)-Arange);
		    state %= 1LL<<31;
		}
		vector<int> R;
		S[0]=0;
		FOR(i,n) {
			S[i+1]=S[i]+Aprefix[i];
		}
		
		if(S[n]<=0) return {-1};
		int cur=0;
		while(cur<n) {
			for(int nex=cur+1;;nex++) {
				if(nex==n || (S[nex]-S[cur]>0 && S[n]-S[nex]>0)) {
					R.push_back(nex-cur);
					cur=nex;
					break;
				}
			}
		}
		
		i=R.size();
		if(R.size()>200) R.resize(200);
		R.insert(R.begin(),i);
		return R;
		
		
	}
}

まとめ

長さを200に切り詰めるところを見落とした人が割といたらしい。