AtCoder ARC #123 : D - Inc, Dec - Decomposition

割と手間取った…。
https://atcoder.jp/contests/arc123/tasks/arc123_d

問題

N要素の整数列Aが与えられる。
この数列を、単調増加な数列Bと単調減少な数列Cの和としたい。
すなわち、A[i]=B[i]+C[i]となるようにしたい。

B[i]

+

C[i]

の総和の最小値を求めよ。

解法

まず、|B[i]|+|C[i]|の総和の最小値の部分を無視してB,Cを仮置きしよう。

• A[0]≧0ならB[0]=A[0]、C[0]=0
• A[0]＜0ならB[0]=0、C[0]=A[0]

とする。
以後、

• A[i-1]≦A[i]なら、B[i]=B[i-1]+(A[i]-A[i-1])、C[i]=C[i-1]
• A[i-1]＞A[i]なら、B[i]=B[i-1]、C[i]=C[i-1]+(A[i]-A[i-1])

とする。こうすると、Bは非負であり、Cは非正である。

以後、Bを全体的にいくつか減らし、Cをいくつか増加させることを考える。
そうするとsum(|B|)やsum(|C|)が小さくなることが期待できる。
B[i]=0となるiやC[j]=0となるjを総当たりし、その際のsum(|B|)やsum(|C|)を適宜更新していって最小値を取ればよい。

int N;
__int128 A[202020];
__int128 B[202020],C[202020],RC[202020];
__int128 SB[202020],SC[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A[i]=x;
	}
	
	__int128 mi=1LL<<62;
	
	
	FOR(j,4) {
		if(A[0]>=0) {
			B[0]=A[0];
			C[0]=0;
			RC[0]=0;
		}
		else {
			B[0]=0;
			C[0]=A[0];
			RC[0]=-A[0];
		}
		SB[1]=B[0];
		SC[1]=RC[0];
		
		for(i=1;i<N;i++) {
			if(A[i]>=A[i-1]) {
				B[i]=B[i-1]+(A[i]-A[i-1]);
				C[i]=C[i-1];
			}
			else {
				B[i]=B[i-1];
				C[i]=C[i-1]+(A[i]-A[i-1]);
			}
			RC[i]=-C[i];
			SB[i+1]=SB[i]+B[i];
			SC[i+1]=SC[i]+RC[i];
		}
		
		
		FOR(i,N) {
			__int128 dif=B[i];
			
			__int128 add=(__int128)(SB[N]-SB[i])-(__int128)dif*(N-i);
			add+=dif*i-SB[i];
			
			dif=A[i]-C[i];
			x=lower_bound(RC,RC+N,dif)-RC;
			add+=(__int128)(SC[N]-SC[x])-(__int128)dif*(N-x);
			add+=(__int128)dif*x-SC[x];
			
			mi=min(mi,add);
		}
		
		if(j==0||j==2) {
			FOR(i,N) A[i]=-A[i];
		}
		if(j==1) {
			reverse(A,A+N);
		}
		
	}
	
	
	cout<<(ll)mi<<endl;
	
	
}

まとめ

本番えらく苦労してるな…。