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; }
まとめ
なんか七面倒な問題。