TopCoderOpen 2021 Regional Qualification Round2 : Div1 Medium MergeToSort

後日試したらMediumでてこずったし、Hardで初回TLEしたので、レート的には出なくて助かった。
https://community.topcoder.com/stat?c=problem_statement&pm=17125&rd=18774

問題

N要素の整数列Aが与えられる。
ここで、隣接する2要素を選び、それらを取り除いてその場所にその和を挿入する、という処理を任意回数行えるとする。
数列が単調増加になるために必要な処理回数は何回か。

解法

隣接する2要素とあるが、いくつか連続した要素をまとめると考えても差し支えない。

f(k) := 整数列のprefix k個に対し、条件に沿うよう処理を行った後、要素数の最大値と、その際の最後の要素はどこからk個目までをまとめたかのpair
とする。解はN-(f(N)における要素数)

となる。
今f(k) = {a,b} とする。
f(k)から、以下のように状態遷移させ最大値を更新しよう。後者はxを二分探索すればよい。

• k+1個目の要素を、k個目とまとめる場合、f(k+1)={a,b}
• 新たな要素を始める場合、単調増加条件を満たす最小のx(sum(A[b...k])≦sum(A[(k+1)...x])となるx)に対し、f(x) = {a+1,k+1}

ll S[202020];
pair<int,int> dp[202020];
class MergeToSort {
	public:
	int minSteps(int N, vector <int> Aprefix, int seed, int blo, int bhi) {
		vector<ll> A;
		FORR(a,Aprefix) A.push_back(a);
		ll state = seed;
		int i;
		while(A.size()<N) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
			int b = blo + ((state / 1000) % (bhi-blo+1));
			state = (state * 1103515245 + 12345) % (1LL<<31);
			int x = 1<<(b-1);
			A.push_back(x + ((state / 10) % x));
		}
		
		ZERO(dp);
		FOR(i,N) S[i+1]=S[i]+A[i];
		dp[0]={1,0};
		
		FOR(i,N) {
			dp[i+1]=max(dp[i],dp[i+1]);
			ll sum=S[i+1]-S[dp[i].second];
			
			if(S[N]-S[i+1]<sum) continue;
			int L=i,R=N;
			while(L+1<R) {
				int M=(L+R)/2;
				if(S[M]-S[i+1]>=sum) R=M;
				else L=M;
			}
			dp[R-1]=max(dp[R-1],{dp[i].first+1,i+1});
		}
		
		return N-dp[N-1].first;
	}
}

まとめ

なんか入力対応で何行も書かされるの、損した気分になるな。