じゃんけん (KUPC 2012)

http://kupc2012.contest.atcoder.jp/tasks/kupc2012_5#

問題

略

解法

解説参照。ソースコードが無駄に複雑なのは誤解等を先に作ったため。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int n;
int mat[300][300];
void ExistAllWin() {
  vector<pair<int, int> > points;
  REP(y, n) {
    int s = 0;
    REP(x, n) {
      s += mat[y][x];
    }
    points.push_back(make_pair(s, y));
  }
  sort(points.rbegin(), points.rend());
  if (points[0].first == 1 + (n - 1) * 3) { points.resize(1); }
  vector<int> candidate;
  REP(i, min(3, (int)points.size())) {
    candidate.push_back(points[i].second);
  }
  if (candidate.size() == 1) {
    REP(i, 1000) {
      printf("%d\n", candidate[0] + 1);
      fflush(stdout);
    }
    exit(0);
  }
}

int main() {
  int v = scanf("%d", &n);
  assert(v == 1);
  REP(y, n) {
    REP(x, n) {
      char c;
      int v = scanf(" %c", &c);
      assert(v == 1);
      mat[y][x] = c == 'o' ? 3 : 0;
    }
    mat[y][y] = 1;
  }

  ExistAllWin();
  int prev = 0;
  REP(i, 1000) {
    printf("%d\n", rand() % n + 1);
    fflush(stdout);
    int v = scanf("%d", &prev);
    assert(v == 1);
  }
}