kmjp's blog

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

Codeforces #685 Div2 F. Nullify The Matrix

Div2最終問にしては後日AC数多め。
https://codeforces.com/contest/1451/problem/F

問題

N*Mのグリッドが与えられる。
初期状態で、各セル非負整数が設定されている。
ここで、以下の2人ターン制ゲームを行う。

  • 自分の手番では、左上マスの値が正であるような矩形領域を選択する。そのような選択ができないなら負けである。
  • その後、左上マスの値を任意の正整数分デクリメントし、その後左上マスから右下マスへの最短路を1つ選ぶ。
    • その際、最短路上で左上マス以外のマスの値を増減させる。マス毎に増減量は異なっていてもよい。
  • ただし、上記手順でどこかのマスで負の値になるような行動はとれない。

両者最適手を取るとき、勝者はどちらか。

解法

f(d) := 行rと列cのうち、r+c=dとなるセルの値のxor
とすると、各dにおけるf(d)がすべて0なら先手の負け、そうでないなら後手の負けである。

というのも、f(d)のxorが0の状態の時、自分の手番でどんな手を取ってもf(d)は非ゼロになるし、逆にf(d)が非ゼロなら全f(d)を1手で全部ゼロにできるためである。

int T;
int H,W,A[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		int num[202]={};
		cin>>H>>W;
		FOR(y,H) FOR(x,W) {
			cin>>A[y][x];
			num[y+x]^=A[y][x];
		}
		FOR(i,202) if(num[i]) break;
		if(i==202) cout<<"Jeel"<<endl;
		else cout<<"Ashish"<<endl;
		
	}
}

まとめ

実装が軽いからupsolveによるACが多いのかな。