Codeforces #768 : Div1 C. Paint the Middle

この回、A,B,C,Dにかかった手間が同じぐらいだな…。
https://codeforces.com/contest/1630/problem/C

問題

N要素の整数列Aが与えられる。
また、初期値が0のN要素の整数列Cを考える。

以下の処理を任意の順で任意回数行えるものとする。

• A[i]=A[k]かつC[i]=C[j]=C[k]=0となるi＜j＜kを指定し、C[j]=1とする。

Cの総和の最大値を示せ。

解法

5***6***5****6のような並びのケースがあったとする。

端から順にみて行って、2つ目の5を見つけたとする。
この時、5と5の間にある6の部分を塗りつぶすかどうか判定することになる。
これは5と5の間にある各要素について、対になる要素がもっと後ろに出てくるのであれば、塗りつぶさずに残す、という処理を繰り返していけばよい。

int N;
int A[202020];
vector<int> P[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[A[i]].push_back(i);
	}
	
	int ret=0;
	for(i=0;i<N;i++) {
		if(P[A[i]].back()==i) continue;
		int L=i;
		int R=P[A[L]].back();
		x=L+1,y=R-1;
		ret+=R-L-1;
		while(1) {
			int ma=R;
			for(j=x;j<=y;j++) {
				ma=max(P[A[j]].back(),ma);
			}
			if(ma==R) break;
			
			L=R;
			R=ma;
			x=L+1,y=R-1;
			ret+=R-L-1;
		}
		
		i=R;
	}
	cout<<ret<<endl;
	
}

まとめ

BもCも細かなミスしそうな問題。