TopCoder SRM 828 : Div1 Medium ContiguousConstantSegment

コーナーケースが面倒。
https://community.topcoder.com/stat?c=problem_statement&pm=17562&rd=19192

問題

N要素の整数列Aと整数Eが与えられる。
Aの1要素を選び、現在値と違う値に変える、という作業をちょうどE回行うとする。
Aの連続部分列のうち、同じ値が連続する列の最大の長さを求めよ。

解法

先にコーナーケースを片付ける。
Aが元々全要素同じ値である場合、かつNが2以上でE=1の場合は、1要素値を書き換えないといけないので解はN-1となる。
N=1またはEが1以外なら、全要素同じ値に戻せるので解はNとなる。

以下、Aが全要素同じでない場合を考える。
これは尺取り法の要領で、区間の左端を定めたときに右端をどこまで伸ばせるかを考えよう。
区間中の*1≦Eであれば、そのような区間の取り方が可能である。
そこで、区間内における各値の登場頻度と、その最大値をヒープなどで管理しながら尺取り法をしていこう。

ll A[252525];
int C[252525];
multiset<int> S;

class ContiguousConstantSegment {
	public:
	int produce(int N, int MOD, vector <int> Aprefix, int seed, int E) {
		int i;
		ll s=seed;
		FOR(i,N) {
			if(i<Aprefix.size()) {
				A[i]=Aprefix[i];
			}
			else {
			    s = (s * 1103515245 + 12345)%(1LL<<31);
			    A[i] = (s / 16)%MOD;
			}
		}
		
		FOR(i,N) if(A[i]!=A[0]) break;
		if(i==N) {
			if(N==1||E>1||E==0) return N;
			return N-1;
		}
		
		
		int L=0,R=0,ma=1;
		ZERO(C);
		S.clear();
		FOR(i,250001) S.insert(0);
		
		for(L=0;L<N;L++) {
			while(R<N) {
				int x=A[R];
				S.erase(S.find(C[x]));
				S.insert(++C[x]);
				int y=*S.rbegin();
				if(R+1-L-y>E) {
					S.erase(S.find(C[x]));
					S.insert(--C[x]);
					break;
				}
				R++;
			}
			ma=max(ma,R-L);
			int x=A[L];
			S.erase(S.find(C[x]));
			S.insert(--C[x]);
		}
		return ma;
	}
}

まとめ

ちょうどE回ではなく、E回以下でもいいと思うんだけど、このコーナーケースは問題の面白さにつながってるのかな…。

*1:区間長)-(最頻値の頻度