AtCoder ARC #119 : E - Pancakes

近い問題見たばっかりだしね…。
https://atcoder.jp/contests/arc119/tasks/arc119_e

問題

整数列Pが与えられる。
ここからある区間を1つ選び、その中身を反転させることができるものとする。
Pにおいて隣接要素の差の絶対値の総和を最小化せよ。

解法

まだここで記事にしていないが、最近でた下記の問題と同等のアプローチが取れる。
F. Swapping Problem

数列中、A,B,.....,C,Dという並びを、A,C......,B,Dと入れ替えた場合に、差の絶対値がどの程度小さくなるか考えよう。
*1かつ[A,B]と[C,D]が共通部分を持つ場合、入れ替えによって共通部分の2倍分だけ差の絶対値の和が減少する。

ここではA,C≦D≦Bの例だけを考えることにする。B≦Dのケースは、左右逆順に処理すればよいし、(A≧BかつA,C≧D)のケースはPの符号を反転させて同様に考えればよい。

隣接要素の対(例えば(A,B)や(C,D))について、後者の値が大きい順に処理し、Range Minimum Queryを解けるSegTreeに前者の値を処理しよう。
B≧Dなので、(A,B)を処理した段階で、SegTreeにはAが格納されている。
(C,D)を処理する場合、RMQにより、Aの存在がわかるので、D-max(C,A)が共通部分のサイズとなる。

int N;
int A[303030];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=(1<<30);
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	ll D=0;
	FOR(i,N-1) {
		D+=abs(A[i]-A[i+1]);
	}
	ll mi=D;
	FOR(i,N-1) {
		ll x=D-abs(A[i]-A[i+1])+abs(A[i]-A[N-1]);
		mi=min(mi,x);
		x=D-abs(A[i]-A[i+1])+abs(A[i+1]-A[0]);
		mi=min(mi,x);
	}
	FOR(i,4) {
		FORR(v,st.val) v=1<<30;
		vector<pair<int,int>> cand;
		FOR(j,N-1) {
			if(A[j]<=A[j+1]) cand.push_back({-A[j+1],j+1});
		}
		sort(ALL(cand));
		
		FORR(c,cand) {
			x=c.second;
			y=st.getval(0,x-1);
			mi=min(mi,D-2*(A[x]-max(A[x-1],y)));
			st.update(x-1,A[x-1]);
		}
		
		FORR(v,st.val) v=1<<30;
		cand.clear();
		FOR(j,N-1) {
			if(A[j]<=A[j+1]) cand.push_back({-A[j+1],-(j+1)});
		}
		sort(ALL(cand));
		FORR(c,cand) {
			x=-c.second;
			y=st.getval(x,N);
			mi=min(mi,D-2*(A[x]-max(A[x-1],y)));
			st.update(x-1,A[x-1]);
		}
		
		
		
		if(i==0||i==2) {
			reverse(A,A+N);
		}
		if(i==1) {
			FOR(j,N) A[j]=(1<<30)-A[j];
		}
	}
	
	
	
	cout<<mi<<endl;
	
}

まとめ

本番場合分けを漏らしてミスをしたのもったいない。

*1:A≦BかつA,C≦D)または(A≧BかつA,C≧D