kmjp's blog

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

Codeforces ECR #054 : G. Array Game

うーむ、これは解けてもよかったな。
http://codeforces.com/contest/1076/problem/G

問題

K要素の正整数列Bを用いて、2人で行うゲームを考える。
数列長に対応したK個のマスが並んでおり、初期状態でコマが1番目のマスにおかれる。この際B[0]はデクリメントされる。

以降、両者交互に以下の手順を行う。
定数Mが与えられているとする。
今コマがi番目のマスにある場合、[i,min(i+M,K)]マスのいずれかに移動する。
ただし移動先のマスをjとしたときB[j-1]が正でなければ移動できず、かつ移動先でB[j-1]はデクリメントされる。
自分のターンで移動できなくなったら負けである。


ここで、N要素の整数列AとMが与えられる。
以下のクエリに答えよ。

  • Aのある部分列A[L..R]に定数Dを加算する。
  • Aのある部分列A[L..R]に対し、上記ゲームを行った場合、両者最適手を取った場合の勝者を答える。

解法

各要素の値の詳細な値は関係なく、いずれも正であること以外には偶奇だけわかっていればよい。
自分の番が回ってきたとき、対応する要素が偶数の場合、その場にとどまる選択肢は取れない(相手が同じ選択肢を取ると、いずれ自分B[j]=0の状態で自分の番が回ってくる)。
よって[i+1,min(i+M,K)]のいずれかに移動しなければならない。
奇数の場合は、その場にとどまってもよいので[i,min(i+M,K)]のどこかに移動すればよい。

よって、自分の番が回ってきたとき勝てるかどうかは、その時点のB[j]の偶奇と[(i+1),min(i+M,K)]のうち必敗な状態があるかどうかで決まる。
必敗な状態があれば、そこに移動させれば相手が負ける、すなわち自分が勝つ。

あとはSegTreeないし平方分割で解く。
以下のコードは平方分割である。分割数をかなり手直ししないとTLEするので注意。
平方分割した各ブロックに対し、その右側M要素の必勝・必敗の組み合わせ2^M通りのbitmaskに対して、ブロック内左端M要素の勝ち負けのbitmaskを返すテーブルを持っておき、前者のクエリ毎に更新する。

前者のクエリはDが偶数なら何もしないと同義で、奇数だと部分列の内容を0/1反転することに対応する。
よって、各ブロック事前に反転後の状態に対するテーブルと、反転の有無を覚えておけば前者のクエリを高速に処理できる。

int N,Q,M;
const int DI=50;
int A[300000];
int dp[10000][2][32];
int S[10000];


inline int nex(int cur,int a) {
	if(a==0) cur = (cur<<1) | 1;
	else cur = (cur<<1) | (cur!=(1<<M)-1);
	return cur&((1<<M)-1);
}

int update(int v,int l,int r) {
	int i,t;
	
	if(S[v]) {
		FOR(i,DI) A[DI*v+i]^=1;
		S[v]=0;
	}
	for(i=l;i<r;i++) A[DI*v+i]^=1;
	
	
	for(int mask=0;mask<1<<M;mask++) {
		
		FOR(t,2) {
			int cur=mask;
			for(i=DI-1;i>=0;i--) cur=nex(cur,A[DI*v+i]^t);
			dp[v][t][mask]=cur;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,N) {
		ll l;
		cin>>l;
		A[i]=l%2;
	}
	FOR(i,250000/DI) update(i,0,0);
	while(Q--) {
		int T,L,R;
		cin>>T>>L>>R;
		L--;
		if(T==1) {
			ll l;
			cin>>l;
			if(l%2==0) continue;
			while(L/DI != R/DI) {
				if(L%DI==0) {
					S[L/DI]^=1;
					L+=DI;
				}
				else {
					update(L/DI,L%DI,DI);
					L+=DI-(L%DI);
				}
			}
			update(L/DI,L%DI,R%DI);
		}
		else {
			int cur=(1<<M)-1;
			while(R>L && R%DI!=0) R--, cur=nex(cur,A[R]^S[R/DI]);
			while(R>=L+DI) R-=DI, cur=dp[R/DI][S[R/DI]][cur];
			while(R>L) R--, cur=nex(cur,A[R]^S[R/DI]);
			
			cout<<2-(cur&1)<<endl;
			
		}
	}
	
	
}

まとめ

うーん、SegTreeにせよ平方分割にせよ、これは解いておきたかった。