コーナーケースが面倒。
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:区間長)-(最頻値の頻度