CodeTON Round 6 : E. Another MEX Problem

微妙な出来。
https://codeforces.com/contest/1870/problem/E

問題

整数列Aが与えられる。
Aのうち互いにオーバーラップしない部分列の集合を選んだ時、各部分列のmex値のxorの最大値を求めよ。

解法

S(n) := 先頭n要素までの部分列のうち、mex値のxorの集合
として愚直にn+1要素目以降の部分列の取り方を総当たりしてよい。
unordered_setやbitsetを使い定数倍高速化をすると間に合う。

int T,N,A[5050];
int num[5050];
unordered_set<int> S[5050];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
		}
		
		FOR(i,N+1) S[i].clear();
		S[0].insert(0);
		FOR(i,N) {
			// skip
			FORR(a,S[i]) S[i+1].insert(a);
			int pre=0;
			int m=0;
			for(y=i+1;y<=N;y++) {
				num[A[y-1]]++;
				while(num[m]) m++;
				if(pre!=m&&m>A[i]&&num[A[i]]==1) {
					FORR(a,S[i]) S[y].insert(a^m);
					pre=m;
				}
			}
			for(y=i+1;y<=N;y++) num[A[y-1]]=0;
		}
		int ma=0;
		FORR(a,S[N]) ma=max(ma,a);
		cout<<ma<<endl;
		
	}
}

まとめ

うーむ微妙。