Codeforces #452 Div2 E. Segments Removal

E,Fは面倒なデータ構造ゲーを1発でAC取れたが、Dを問題文解釈間違えて地味に手間取った。
http://codeforces.com/contest/899/problem/E

問題

整数列が与えられる。
この列のうち、同じ数値が連続している部分列において、最長のうち最も右の物を取り除く、という処理を繰り返すとき、数列が空になるまで何回処理が必要か。

解法

前後の要素をくっつけたり間をくりぬいたりする処理があるときはsetを使うことを検討しよう。
自分は以下の２種類のsetを用いた。

• 現在の数列で残っている要素において、端から順に見たとき新たな要素が始まるindexのset（indexは元の数列におけるindexであり、減少後ではない）
• 上記indexと、そのindexを先頭とする同じ要素が連続する数のpairのset。後者の値をpairのfirstに入れることで、最長の物を高速に取り出せる。

後者のsetより取り除く対象がわかり、前者のsetよりその前後の要素のindexがわかるので元整数列における値が等しいなら連結する、という処理を繰り返す。

int N;
int A[202020];
int num[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int pre=-1;
	FOR(i,N) {
		cin>>A[i];
		if(pre==-1 || A[pre]!=A[i]) pre=i;
		num[pre]++;
	}
	set<int> P;
	set<pair<int,int>> cand;
	FOR(i,N) if(num[i]) {
		P.insert(i);
		cand.insert({-num[i],i});
	}
	
	int step=0;
	while(P.size()) {
		step++;
		x=cand.begin()->second;
		cand.erase(cand.begin());
		
		P.erase(x);
		auto it=P.lower_bound(x);
		if(it==P.begin()||it==P.end()) continue;
		y=*it;
		it--;
		x=*it;
		if(A[x]==A[y]) {
			P.erase(y);
			cand.erase({-num[y],y});
			cand.erase({-num[x],x});
			num[x]+=num[y];
			cand.insert({-num[x],x});
		}
	}
	
	cout<<step<<endl;
	
}

まとめ

結構ありそうな問題。