Codeforces #543 Div1 A. Diana and Liana

Unratedだった回。
https://codeforces.com/contest/1120/problem/A

問題

M要素の数列が与えられる。
ここからいくつかの要素を取り除いた後、先頭からK要素の部分列をN個抜き出す。

ここで、さらに別の数列Bが与えられる。
N個の部分列のうち、Bを(並び順不問で)包含するものが1個以上あるようにするためには、何を取り除けばよいか。

解法

尺取り法の要領で、Bを包含する部分列について、左端を走査しながらが右端を求めよう。
あとは残りの領域から部分列を(N-1)個取れそうなら、そこが解の一例となる。

int M,K,N,S;
int A[505050];
map<int,int> need,need2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d%d",&M,&K,&N,&S);
	FOR(i,M) scanf("%d",&A[i]);
	FOR(i,S) {
		scanf("%d",&x);
		need[x]++;
	}
	need2=need;
	
	
	int over=need.size();
	int L,R=0;
	FOR(L,M) {
		while(R<M && (over>0 || R-L<K)) {
			need[A[R]]--;
			if(need[A[R]]==0) over--;
			R++;
		}
		if(over==0 && L/K+(M-R)/K>=N-1) {
			vector<int> ret;
			int add=min(N-1,L/K);
			N-=add;
			FOR(i,L-add*K) ret.push_back(i);
			add=min(N-1,(M-R)/K);
			N-=add;
			FOR(i,M-R-add*K) ret.push_back(M-1-i);
			
			vector<int> C;
			for(i=L;i<R;i++) {
				if(need2[A[i]]) {
					need2[A[i]]--;
				}
				else {
					C.push_back(i);
				}
			}
			C.resize(R-L-K);
			FORR(c,C) ret.push_back(c);
			
			sort(ALL(ret));
			cout<<ret.size()<<endl;
			FORR(r,ret) cout<<(r+1)<<" ";
			return;
			
		}
		
		if(need[A[L]]==0) over++;
		need[A[L]]++;
	}
	
	cout<<-1<<endl;
	
	
	
}

まとめ

なんか七面倒な問題。