Codeforces ECR #005 : D. Longest k-Good Segment

Eをこじらせてだいぶ遅れた。Dまではまぁまぁ。
http://codeforces.com/contest/616/problem/D

問題

数列Aがある。
数列がK-goodであるとは、数列内に登場する要素がK種以下であることを意味する。
Aの連続部分列のうち、最長なK-good数列となるものを求めよ。

解法

尺取法の要領で、連続部分列の末尾を後ろに１ずつずらしながら、登場する要素がK種以下になるよう先頭をずらしていく。
部分列中に登場する各要素の数を配列で数えておき、0と1を跨ぐときに、要素の種類が増減すると考えるとよい。

int N,K;
int A[505050];

int num[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	
	int L=0,R=0;
	int p=1;
	num[A[0]]=1;
	x=0;
	for(y=1;y<N;y++) {
		if(num[A[y]]++==0) p++;
		while(p>K) if(--num[A[x++]]==0) p--;
		if(y-x>R-L) R=y,L=x;
	}
	
	cout<<(L+1)<<" "<<(R+1)<<endl;
}

まとめ

D,E,Fの難易度が極端に差がある。