AtCoder ARC #165 : F - Make Adjacent

ARCのボス問にしてはコードが短いかも？
https://atcoder.jp/contests/arc165/tasks/arc165_f

問題

1～Nを2個ずつ含む数列Aが与えられる。
1～Nを2個ずつ含む数列Xが良いとは、同じ値は隣接した位置にあることを示す。

Aを良い数列にするため、隣接2要素のswapを行う最小回数をKとする。
K回のswapで作れる良い数列のうち、辞書順最小のものを求めよ。

解法

2値の並びが

• A...A....B....Bの場合、AA...BBにするのがswap回数が少ない。
• A...B....A....Bの場合、AA...BBにするのがswap回数が少ない。
• A...B....B....Aの場合、AA...BBでもBB...AAでもswap回数が同じ

1つ目と2つ目のパターンは、AとBの並びは変えられない。
3つ目のパターンになっている2値の並びの関係を見たら、A,Bのうち小さいものを手前に持ってくるようにしよう。
これはSegTreeを用いた平面走査で判定できる。

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){
		pair<V,int> a=l;
		a.first.first=min(l.first.first,r.first.first);
		if(l.first.first>r.first.second) {
			a.first.second=r.first.second;
			a.second=r.second;
		}
		return a;
	}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(make_pair(1<<30,1<<30),1<<30);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_Pair<pair<int,int>,1<<20> st;
int N;
int A[404040];
int L[202020],R[202020];
int num[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(L);
	cin>>N;
	FOR(i,2*N) {
		cin>>A[i];
		A[i]--;
		if(L[A[i]]<0) {
			L[A[i]]=i;
		}
		else {
			R[A[i]]=i;
		}
	}
	FOR(i,2*N) {
		if(L[A[i]]==i) {
			st.update(i,{R[A[i]],R[A[i]]});
		}
	}
	set<int> cand;
	while(1) {
		while(1) {
			auto p=st.val[1];
			i=p.second;
			if(p.first.second==1<<30) break;
			cand.insert(A[i]);
			st.update(i,{R[A[i]],1<<30});
		}
		if(cand.empty()) break;
		x=*cand.begin();
		cand.erase(x);
		cout<<x+1<<" "<<x+1<<" ";
		st.update(L[x],{1<<30,1<<30});
	}
	cout<<endl;
}

まとめ

ARCのボス問にしては易しめ？