TopCoder SRM 729 Div1 Hard XorAndLIS

これはシンプルな問題設定ながら面白かったです。
https://community.topcoder.com/stat?c=problem_statement&pm=14718

問題

N要素の整数列X[i]が与えられる。
この数列に対し、任意の回数任意の順番でX[i+1]←X[i+1] xor X[i]で値を更新できるとする。

その後LISを取る場合、最適に値を更新した場合のLISの長さを求めよ。

解法

xorを任意回数任意順で実行できるということは、X[i]の値はX[i]にX[0]～X[i-1]の値を任意回数xor取れるということである。
もっと言えば、X[0]～X[i-1]をビットベクトルとして考えた場合に掃出し法で基底ベクトルを求めておけば、各基底ベクトルをX[i]に加える(xor)かどうかを任意に決定できる。

以下を考える。
f(i,k) := Xの先頭i要素からk要素のLISを構築する場合の最後尾の値の最小値、ただしそのような値がない場合inf
f(N,k)としてinfでない最大のkが解となる。

i番目の要素をLISに加えるかどうかを考えると、この値は以下のようにDPで計算できる。
f(i,k) := min(f(i-1,k), g(i,f(i-1,k-1)+1))

g(i,v) := X[i]に対しX[0]～X[i-1]をxorして得られるv以上の値のうち最小値
とする。
X[i]を処理する際、上記のとおりX[0]～X[i-1]は先に掃出し法で基底ベクトルに分解できていたとする。
X[i]に基底ベクトルを大きい順にxor取るかどうかを判断する。
その際、v以上となる場合の最小値と、v未満となる場合の最大値を適宜更新していくと、最終的にv以上となる場合の最小値がg(i,v)となる。

ll dp[102][102];

class XorAndLIS {
	public:
	vector<ll> X;
	int N;
	
	void hogege(int n) {
		if(n==0) return;
		sort(X.begin(),X.begin()+n);
		if(X[n-1]==0) return;
		ll v=0;
		for(int i=0;i<=61;i++) if(X[n-1]&(1LL<<i)) v=1LL<<i;
		for(int i=0;i<n-1;i++) if(X[i]&v) X[i]^=X[n-1];
		hogege(n-1);
	}
	
	ll hoge(ll A,ll B,int d) {
		if(A>=1LL<<60) return A;
		if(A==B) return B;
		ll L,R;
		if(A<B) L=-1,R=B;
		if(A>B) L=B,R=1LL<<60;
		
		while(d>=0) {
			ll LL=L,RR=R;
			if((LL^X[d])>=A) R=min(R,(LL^X[d]));
			if((LL^X[d])<A)  L=max(L,(LL^X[d]));
			if((RR^X[d])>=A) R=min(R,(RR^X[d]));
			if((RR^X[d])<A)  L=max(L,(RR^X[d]));
			d--;
		}
		
		return R;
	}
	
	int maximalLength(vector<long long> v) {
		X=v;
		
		N=X.size();
		int i,x,y;
		FOR(x,101) FOR(y,101) dp[x][y]=1LL<<60;
		dp[0][0]=-1;
		FOR(i,N) {
			hogege(i);
			FOR(x,N+1) {
				dp[i+1][x]=min(dp[i+1][x],dp[i][x]);
				if(x) dp[i+1][x]=min(dp[i+1][x],hoge(dp[i][x-1]+1,X[i],i-1));
			}
		}
		
		
		for(i=N;i>=0;i--) if(dp[N][i]<1LL<<60) return i;
		
		return 0;
		
	}
}

まとめ

本番g(i,v)をもっとややこしい方法で計算していたので、計算量がちょっと不安だったけど通ってよかった。