Codeforces ECR #095 : G. Three Occurrences

意外にシンプルなんだな。
https://codeforces.com/contest/1418/problem/G

問題

整数列Aが与えられる。
Aの連続した部分列のうち、同じ値が3回ずつ登場するようなものは何通りか。

解法

ハッシュで解く。
f(c,k) := 文字cが3n+k回登場したときの対応するハッシュ値
とする。
H(n) := 先頭n文字に現れる各文字cとその登場回数C(c)に対し、f(c,C(c)%3)の総和
とすると、解はH(L)=H(R)かつA[L]～A[R-1]に同じ値が4回以上登場しないものとなる。

Rに対し、H(L)=H(R)となるLの数はハッシュ値をキーとするmapで数え上げられる。
「同じ値が4回以上登場しない」の条件は、Rを総当たりしつつ尺取り法の要領でLの左端を動かしていけばよい。

int N;
int A[505050];
ll S[505050][2][2];
int num[505050];
vector<int> pos[505050];

ll P[505050][2];
const ll mo1=1000000009;
const ll mo2=1000000021;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	P[0][0]=P[0][1]=1;
	FOR(i,N) {
		P[i+1][0]=P[i][0]*((1<<20)+5)%mo1;
		P[i+1][1]=P[i][1]*((1<<20)+rand()%1000)%mo2;
	}
	
	int ma=0;
	map<pair<pair<ll,ll>,pair<ll,ll>>,int> M;
	M[{{0LL,0LL},{0LL,0LL}}]++;
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		
		S[i+1][0][0]=S[i][0][0];
		S[i+1][0][1]=S[i][0][1];
		S[i+1][1][0]=S[i][1][0];
		S[i+1][1][1]=S[i][1][1];
		
		
		if(num[x]==1) {
			(S[i+1][0][0]+=mo1-P[x][0])%=mo1;
			(S[i+1][0][1]+=mo2-P[x][1])%=mo2;
		}
		if(num[x]==2) {
			(S[i+1][1][0]+=mo1-P[x][0])%=mo1;
			(S[i+1][1][1]+=mo2-P[x][1])%=mo2;
		}
		num[x]=(num[x]+1)%3;
		if(num[x]==1) {
			(S[i+1][0][0]+=P[x][0])%=mo1;
			(S[i+1][0][1]+=P[x][1])%=mo2;
		}
		if(num[x]==2) {
			(S[i+1][1][0]+=P[x][0])%=mo1;
			(S[i+1][1][1]+=P[x][1])%=mo2;
		}
		
		if(pos[x].size()>=3) {
			y=pos[x][pos[x].size()-3];
			while(ma<y) {
				pair<pair<ll,ll>,pair<ll,ll>>  a={{S[ma][0][0],S[ma][0][1]},{S[ma][1][0],S[ma][1][1]}};
				M[a]--;
				ma++;
			}
		}
		pos[x].push_back(i+1);
		
		pair<pair<ll,ll>,pair<ll,ll>>  a={{S[i+1][0][0],S[i+1][0][1]},{S[i+1][1][0],S[i+1][1][1]}};
		ret+=M[a];
		M[a]++;
		
		
	}
	cout<<ret<<endl;
	
	
}

まとめ

Fに比べると素直な問題かな。