UVa 12409 Kisu Pari Na – 1

UVa ゲーム

問題

n x mのマスのそれぞれにコインがa[i][j]枚置いてある。
これを使って次のようなゲームをする。

  • 先手後手が交互に手番を持つ。
  • 手番のプレイヤーは、コインが一枚以上置いてあるマスを選び、コインを好きな枚数だけ選ぶ。
  • 選んだコインを、下または右のマスへ移動させる（分けて移動させることはできない）
  • 最下段および最右列のコインはそれ以上下、右へ移動させることはできない。
  • 動かせなくなったプレイヤーの負け。

このとき、お互いが最善を尽くした場合どちらのプレイヤーが勝つかを求めよ。

制約条件

n x m≦50000
a[i][j]≦10^9

方針

右下までコインを動かすのに、偶数手かかるマスについて考える。
相手にこのマスにあるコインをk枚動かされたとき、
自分はそのk枚のコインを再度右または下に動かすことができる。


したがって、偶数手かかるマスのみにコインがある場合後手が真似戦略が出来るため、
偶数手かかるマスにコインはないものと考えてよい。


すると、奇数手かかるマスからコインを動かすのはゲームからそのコインを取り除くのと等しいため、
これは奇数手の山でNimをしていることに相当する。

ソースコード

int main(){
    int CS;
    scanf("%d", &CS);
    rep(cs, CS){
        int h, w;
        scanf("%d%d", &h, &w);
        ll sum = 0;
        rep(i, h) rep(j, w){
            ll t;
            scanf("%lld", &t);
            if((h - i + w - j) % 2) sum ^= t;
        }
        printf("Case %d: %s\n", cs + 1, sum ? "win" : "lose");
    }
    return 0;
}