kmjp's blog

競技プログラミング参加記です

Pinely Round 2 : F. Divide, XOR, and Conquer

こっちの方がコードは短い。
https://codeforces.com/contest/1863/problem/F

問題

N要素の整数列Aが与えられる。
整数を前半分と後ろ半分に分け、それぞれxorの値が大きくなる方を残す(等しい場合はどちらを選んでもよい)とする。
各要素を、最後の1個として残せるかを判定せよ。

解法

f(L,R) := A[L...R]を残すことができるか
このテーブルを、区間の長い順に埋めることを考える。

f(L,R)がTrueになるには、以下のいずれかを満たせばよい。

  • f(X,L-1)がTrueかつxor(A[X...(L-1)])≦A[L,R]
  • f(R+1,Y)がTrueかつxor(A[(R+1)...Y])≦A[L,R]

xorの内側の部分について、X,Yを毎回総当たりしたくないので、L,Rに対するxorの最小値を覚えておこう。

int T,N;
ll A[10101];
ll X[10101];
ll Lmask[10101],Rmask[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> G;
		FOR(i,N) {
			cin>>A[i];
			X[i+1]=X[i]^A[i];
			G.insert(i);
		}
		FOR(i,N+1) {
			Lmask[i]=Rmask[i]=0;
		}
		
		for(int len=N;len>=1;len--) {
			for(int L=0;L+len<=N;L++) {
				ll v=X[L+len]^X[L];
				int ok=(len==N)||(v&Lmask[L])||(v&Rmask[L+len]);
				if(Lmask[L]&(1LL<<61)) ok=1;
				if(Rmask[L+len]&(1LL<<61)) ok=1;
				if(len==1) {
					cout<<ok;
					continue;
				}
				if(ok==0) continue;
				if(v==0) {
					Lmask[L]|=1LL<<61;
					Rmask[L+len]|=1LL<<61;
				}
				else {
					x=63-__builtin_clzll(v);
					ll w=1LL<<x;
					Lmask[L]|=w;
					Rmask[L+len]|=w;
				}
			}
		}
		cout<<endl;
	}
}

まとめ

このコード、テストは通ってるけどちょっと自信なくなってきた。