Codeforces ECR #055 : E. Increasing Frequency

これはシンプルながら悩ましくていい問題。
https://codeforces.com/contest/1082/problem/E

問題

整数列A[i]と整数Cが与えられる。
このうちある1つの任意の部分列に対し、各要素に同じ数値(正負を問わない)を加算できる。

そうしてA中におけるCの数を最大いくつにできるか。

解法

A[i]において、ある整数Bを含む区間にC-Bを加算してCの数を最大化することを考えよう。
まずA[i]においてC以外の数を列挙して要素毎にグループ化し、同じA[i]同士をまとめておいてそれらをBとして総当たりする。

Bを含むある区間にC-Bを加算すると、区間内のBがCになる一方、もともとCであった要素はCでなくなってしまう。
よって前者の恩恵が後者の損失を大きく上回るタイミングを求めよう。

以下の数列を考える。
Bの登場回数だけ1が入り、1と1の間には、対応するBとBの間に登場するCの数のマイナス値を置く。
この数列の部分和のうち最大なものを選択すれば、すなわち前者の恩恵が後者の損失を最も上回ることになる。
部分和の最大値の求め方は、累積和の最小値と最大値の差を取ればO(数列長)で行うことができるので、全体でO(|A|)で済む。

int N,C;
int A[1010101];
int S[1010101];
vector<int> V[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&C);
	FOR(i,N) {
		scanf("%d",&A[i]);
		S[i+1]=S[i]+(A[i]==C);
		if(A[i]!=C) V[A[i]].push_back(i+1);
	}
	
	int ma=S[N];
	for(i=1;i<=500000;i++) if(V[i].size()) {
		int ok=1;
		int cur=1;
		int mi=0;
		for(j=1;j<V[i].size();j++) {
			cur-=S[V[i][j]]-S[V[i][j-1]];
			mi=min(mi,cur);
			cur++;
			ok=max(ok,cur-mi);
		}
		ma=max(ma,S[N]+ok);
		
	}
	
	cout<<ma<<endl;
	
}

まとめ

ちょっと迷ったけど綺麗に解けて良かった。