UVa 12729 : Squares Game

問題リング : [uva.onlinejudge.org/external/127/12729.pdf:title]

問題概要 :
H * W のグリッドがあり、初期状態では各マスに色はついていない
AnaとBobがゲームをする
最初のターンはAnaが行う
Anaは色が付いていない2*2のマスを選び赤で塗りつぶす
Bobは色が付いていないマスを１つ選び青で塗りつぶす
塗れるマスがない場合はスキップする
全てのマスに色がついたらゲーム終了
沢山色を塗れた人が勝利
両者が最善を尽くしたとき勝利するのはどちらか？

解法 :
Anaは左上から規則正しく塗っていくほかない
中途半端に塗ると余計塗れる場所がなくなる

********
********

こんなときは

AA**AA**
AA*BAA*B

こんな感じで塗るほか無い
AはAnaで
BはBob

**
** のうちBobが塗るべきは右下

それ以外だとAnaに余計に塗られてしまう

そう思ったのでそんなコードを書いた

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define ANA true
#define BOB false

int H,W;
bool isValid(int x,int y) { return 0 <= x && x < W && 0 <= y && y < H; }

int main(){
  int T,CNT=1;
  cin >> T;
  while( T-- ){
    cin >> H >> W;
    printf("Case #%d: ",CNT++);
    int Ana = 0;
    int x = 1,y = 1;
    bool phase = ANA;
    while( isValid(x,y) ){
      if( phase == ANA ) Ana += 4;
      x += 2;
      if( x >= W ) { y += 2; x = 1; }
      phase = !phase;
    }
    if( Ana == H*W-Ana ) puts("Draw");
    else if( Ana > H*W-Ana ) puts("Ana");
    else puts("Bob");
  }
  return 0;
}