Codeforces #866 : Div1 D. Misha and Apples

問題文が読みにくいな…。
https://codeforces.com/contest/1819/problem/D

問題

整数N,Mが与えられる。
1～Nの整数値の部分集合であるSが与えられる。

以下のM個のクエリに順次答えて行くとする。

• 数列が与えられるので、その内容をSに加える。ただし、Sに同じ整数値が2個以上含まれた場合、Sは空になる。
• 不定な数列が与えられる。その内容は1～Nの部分集合からなる任意の数列を取れるとする。その内容をSに加える。ただし、Sに同じ整数値が2個以上含まれた場合、Sは空になる。

不定な数列の内容を適切に選んだ時、最終的なSの要素数の最大値を求めよ。

解法

DPで各クエリ番号iに対し以下を求める。

• i番目のクエリを終わった時点で、Sを空にできるかどうか
• i番目のクエリを終わった時点でSが空である場合、そこから以降のクエリを処理して最大何要素Sに含められるか。

前者は、不定な数列なら絶対trueだし、そうでなければ過去に同じ要素が現れるクエリ番号を覚えていれば計算できる。

int T,N,M;
int K[202020];
vector<int> V[202020];

int Z[202020],prez[202020],MC[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		map<int,int> pre;
		
		Z[0]=1;
		int ng=-1;
		MC[0]=0;
		FOR(i,N) {
			MC[i+1]=0;
			Z[i+1]=0;
			cin>>K[i];
			V[i].resize(K[i]);
			FORR(a,V[i]) {
				cin>>a;
			}
			
			if(K[i]==0) {
				Z[i+1]=1;
				pre[0]=i;
			}
			else {
				int prep=pre.count(0)?pre[0]:-1;
				int nng=ng;
				FORR(v,V[i]) {
					prep=max(prep,pre.count(v)?pre[v]:-1);
					nng=max(nng,pre.count(v)?pre[v]:-1);
					pre[v]=i;
				}
				if(prep!=-1&&ng<prez[prep]) Z[i+1]=1;
				ng=nng;
			}
			
			if(Z[i+1]) {
				prez[i+1]=i+1;
			}
			else {
				prez[i+1]=prez[i];
			}
		}
		
		int ma=0;
		set<int> did;
		int num=0;
		for(i=N-1;i>=0;i--) {
			if(K[i]==0) did.insert(0);
			int ng=0;
			FORR(v,V[i]) {
				if(did.count(v)) {
					ng=1;
				}
				did.insert(v);
				num++;
			}
			if(ng) break;
			if(Z[i]) {
				if(did.count(0)) {
					ma=M;
				}
				else {
					ma=max(ma,num);
				}
			}
		}
		
		cout<<ma<<endl;
		
		
		
	}
}

まとめ

これ問題はそこまで複雑じゃないのに、なんか問題文読みにくいな。