AtCoder ARC #134 : D - Concatenate Subsequences

中盤で手間取って、後半解ける問題落とすのどうにかしたい。
https://atcoder.jp/contests/arc134/tasks/arc134_d

問題

長さ2Nの整数列Aが与えられる。
空でない1～Nの部分列Xに対し、A[X[1]],A[X[2]],...A[X[|X|]],A[X[1]+N],A[X[2]+N],...A[X[|X|]+N]を抜き出したとき、辞書順最小のものは何か。

解法

A[1...X]の最小値をsとする。
A[i]=sとなるN以下のiうち、A[i+N]≦sとなるものがあれば、A[i+N]が最小となるiに対し、X=[i]が解となる。
そうでない場合、すなわちA[i]=sとなるすべてのiに対し、A[i+N]=t＞sであれば、A[1...N]のうち、s≦A[X[i]]≦tかつA[X[i]]≦A[X[i+1]]となるような最長のXを取ってみよう。

問題は、A[X[i]]=tとなるX[i]を、X中に残すかどうかである。
これは、A[X[j]]＜tとなるX[1...m]に対し、[t、A[X[1+N]]、A[X[2+N]]…]が[t,t,t,...]より小さいなら、A[X[i]]=tとなるX[i]をXから取り除き、早く求める数列にt未満の値が来るようにした方がよい。

int N;
pair<int,int> P[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i].first;
	}
	FOR(i,N) {
		cin>>P[i].second;
	}
	
	vector<int> A,B;
	A={P[0].first};
	B={P[0].second};
	for(i=1;i<N;i++) {
		
		while(A.size()&&(A.back()>P[i].first)) {
			A.pop_back();
			B.pop_back();
		}
		A.push_back(P[i].first);
		B.push_back(P[i].second);
	}
	
	while(A.back()!=A[0]&&A.back()>B[0]) {
		A.pop_back();
		B.pop_back();
	}
	x=1<<30;
	FOR(i,A.size()) if(A[i]==A[0]) x=min(x,B[i]);
	if(x<=A[0]) {
		cout<<A[0]<<" "<<x<<endl;
		return;
	}
	int del=1;
	for(i=1;i<A.size();i++) {
		if(A[i]!=B[0]) {
			if(B[i]>B[i-1]) {
				del=0;
				break;
			}
			if(B[i]<B[i-1]) {
				del=1;
				break;
			}
		}
	}
	FOR(i,A.size()) {
		if(A[i]==B[0]&&del) continue;
		cout<<A[i]<<" ";
	}
	FOR(i,A.size()) {
		if(A[i]==B[0]&&del) continue;
		cout<<B[i]<<" ";
	}
	cout<<endl;
}

まとめ

時間かかりすぎた…。