Codeforces #777 : Div2 E. Gojou and Matrix Game

久々にこれ使った。
https://codeforces.com/contest/1658/problem/E

問題

N*Nの盤面を使う2人対戦ゲームを考える。
各セルには異なる整数値が設定されている。

あるマスにトークンが置かれている状態で、両者交互にトークンを動かす。
その際、マンハッタン距離がK以上の場所に動かさなければならない。
また、移動後はそのマスに書かれた値の分スコアを得る。

10^100ターン後、より多くのスコアを得るのは先手後手どちらか。

解法

初手で現在より大きな値のマスに到達できれば、先手必勝。
そうでなければ、後手が毎回元の位置にトークンを戻すので必敗。

よって「現在より大きな値のマスに到達」を判定できればよい。
これは2D-BITやSegTreeで矩形区間内にある、現在位置より大きな値のマス数を数えればよい。

int N,K;
int V[2020][2020];

template<class V,int MA> class BIT_2d {
public:
	V val[1<<MA][1<<MA];
	BIT_2d(){ZERO(val);};
	V total(int x,int y) {
		V s=0;
		for(int i=x+1;i>0;i-=i&-i) for(int j=y+1;j>0;j-=j&-j) s+=val[i-1][j-1];
		return s;
	}
	void update(int x,int y,V v) {
		for(int i=x+1;i<=1<<MA;i+=i&-i) for(int j=y+1;j<=1<<MA;j+=j&-j) val[i-1][j-1]+=v;
	}
};
BIT_2d<int,12> bit;

int win[2020][2020];


void solve() {
	int i,j,l,r,x,y; string s;
	
	cin>>N>>K;
	vector<pair<int,int>> P;
	FOR(y,N) FOR(x,N) {
		cin>>V[y][x];
		P.push_back({-V[y][x],y*2000+x});
	}
	sort(ALL(P));
	FORR2(a,b,P) {
		y=b/2000;
		x=b%2000;
		int p=x+y+1;
		int q=x-y+2000+1;
		
		int tot=bit.total((1<<12)-1,(1<<12)-1);
		int p2=min(p+K,4040),p1=max(p-K-1,0);
		int q2=min(q+K,4040),q1=max(q-K-1,0);
		tot-=bit.total(p2,q2)-bit.total(p1,q2)-bit.total(p2,q1)+bit.total(p1,q1);
		if(tot==0) {
			win[y][x]=1;
			bit.update(p,q,1);
		}
	}
	
	FOR(y,N) {
		FOR(x,N) cout<<(win[y][x]?'M':'G');
		cout<<endl;
	}
	
}

まとめ

2DBIT、久々。