こっちの方がコードは短い。
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; } }
まとめ
このコード、テストは通ってるけどちょっと自信なくなってきた。