AOJ2241 Usaneko Matrix

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2241

2人でN*Nのビンゴゲームを行う。マスの各値は互いに異なり、コールされる値もまた互いに異なる。
勝つ条件として、うさぎはU以上の列を揃える必要があり、ねこはV以上の列を揃える必要がある。
勝つのはどちらか、また勝者が決まらない場合は引き分けとせよ。
N <= 500
コールされる回数 <= 100000
書かれる値 <= 1000000

解法

書かれる値に対して、その位置を返す配列を各々に対して用意する。
行、列、2つの対角線でそれぞれN個揃った時にカウントしていく。
ただこの方法だと、ビンゴが1マスのみのとき、コールされた値と一致した時に4とカウントしてしまう落とし穴があるので、N=1ののみを例外処理する。

int usagi[1000001];
int neko[1000001];
int Ru[500], Cu[500], Du[2];
int Rn[500], Cn[500], Dn[2];
 
int main() {
 
  int N, U, V, M; cin >> N >> U >> V >> M;
  rep(i, 1000001) usagi[i] = neko[i] = -1;
  rep(i, N) rep(j, N) {
    int x; scanf("%d", &x);
    usagi[x] = i * N + j;
  }
  rep(i, N) rep(j, N) {
    int x; scanf("%d", &x);
    neko[x] = i * N + j;
  }
 
  int u = 0, v = 0;
 
  rep(_, M) {
    int card; scanf("%d", &card);
    if(~usagi[card]) {
      int a = usagi[card] / N; Ru[a]++;
      int b = usagi[card] % N; Cu[b]++;
      if(a == b) Du[0]++;
      if(a == N-1-b) Du[1]++;
      if(Ru[a] == N) u++, Ru[a] = -1;
      if(Cu[b] == N) u++, Cu[b] = -1;
      if(Du[0] == N) u++, Du[0] = -1;
      if(Du[1] == N) u++, Du[1] = -1;
    }
    if(~neko[card]) {
      int a = neko[card] / N; Rn[a]++;
      int b = neko[card] % N; Cn[b]++;
      if(a == b) Dn[0]++;
      if(a == N-1-b) Dn[1]++;
      if(Rn[a] == N) v++, Rn[a] = -1;
      if(Cn[b] == N) v++, Cn[b] = -1;
      if(Dn[0] == N) v++, Dn[0] = -1;
      if(Dn[1] == N) v++, Dn[1] = -1;
    }
    if(N == 1) {
      u = min(1, u), v = min(1, v);
      if(!((u == 1 && U == 1) || (v == 1 && V == 1))) continue;
      if(u == 1 && v == 1 && U == V && U == 1) {
        cout << "DRAW" << endl;
        return 0;
      }
      else if(u == 1 && U == 1) {
        cout << "USAGI" << endl;
        return 0;
      }
      else if(v == 1 && V == 1) {
        cout << "NEKO" << endl;
        return 0;
      }
      else {
        cout << "DRAW" << endl;
        return 0;
      }
    }
    else if(U <= u && V > v) {
      cout << "USAGI" << endl;
      return 0;
    }
    else if(U > u && V <= v) {
      cout << "NEKO" << endl;
      return 0;
    }
    else if(U <= u && V <= v) {
      break;
    }
  }
 
  cout << "DRAW" << endl;
   
  return 0;
}