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が多いのかな。