GCJ 2016 Round 1A B: Rank and File

問題

Dashboard - Round 1A 2016 - Google Code Jam

解法

あるiについて、(0, 0)と(i, i) を頂点とする正方形を作ると、必ず(i, i)が正方形の中で最大値になる。この性質を利用する。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

bool insertb(bool is_row, int insert_pos, const vector<int> &list,
             vector<vector<int>> &board) {
  int N = list.size();
  if (is_row) {
    for (int i = 0; i < N; ++i) {
      if (insert_pos > 0 && board[insert_pos - 1][i] >= list[i]) return false;
      if (insert_pos < N - 1 && board[insert_pos + 1][i] <= list[i] &&
          board[insert_pos + 1][i] > 0)
        return false;
      if (board[insert_pos][i] > 0 && board[insert_pos][i] != list[i])
        return false;
    }
    for (int i = 0; i < N; ++i) board[insert_pos][i] = list[i];
    return true;
  }

  for (int i = 0; i < N; ++i) {
    if (insert_pos > 0 && board[i][insert_pos - 1] >= list[i]) return false;
    if (insert_pos < N - 1 && board[i][insert_pos + 1] <= list[i] &&
        board[i][insert_pos + 1] != 0)
      return false;
    if (board[i][insert_pos] > 0 && board[i][insert_pos] != list[i])
      return false;
  }
  for (int i = 0; i < N; ++i) board[i][insert_pos] = list[i];
  return true;
}

bool ans_is_row;
int ans_row;

bool rec(int pos, vector<bool> &used, vector<vector<int>> &board,
         const vector<vector<int>> &lists) {
  if (pos == -1) return true;
  vector<int> maxs;
  int ma = 0;
  for (int i = 0; i < lists.size(); ++i) {
    if (used[i]) continue;
    chmax(ma, lists[i][pos]);
  }

  for (int i = 0; i < lists.size(); ++i) {
    if (lists[i][pos] == ma) {
      maxs.push_back(i);
    }
  }

  if (maxs.size() == 2) {
    {
      vector<vector<int>> copy_board = board;
      if (insertb(true, pos, lists[maxs[0]], board) &&
          insertb(false, pos, lists[maxs[1]], board)) {
        used[maxs[0]] = true;
        used[maxs[1]] = true;
        if (rec(pos - 1, used, board, lists)) return true;
      }
      used[maxs[0]] = false;
      used[maxs[1]] = false;
      board.swap(copy_board);
    }
    {
      vector<vector<int>> copy_board = board;
      if (insertb(true, pos, lists[maxs[1]], board) &&
          insertb(false, pos, lists[maxs[0]], board)) {
        used[maxs[0]] = true;
        used[maxs[1]] = true;
        if (rec(pos - 1, used, board, lists)) return true;
      }
      used[maxs[0]] = false;
      used[maxs[1]] = false;
      board.swap(copy_board);
    }

    return false;

  } else if (maxs.size() == 1) {
    ans_row = pos;
    int maxi = maxs[0];
    {
      vector<vector<int>> copy_board = board;
      if (insertb(true, pos, lists[maxi], board)) {
        used[maxi] = true;
        if (rec(pos - 1, used, board, lists)) {
          ans_is_row = false;
          return true;
        }
      }
      used[maxi] = false;
      board.swap(copy_board);
    }
    {
      vector<vector<int>> copy_board = board;
      if (insertb(false, pos, lists[maxi], board)) {
        used[maxi] = true;
        if (rec(pos - 1, used, board, lists)) {
          ans_is_row = true;
          return true;
        }
      }
      used[maxi] = false;
      board.swap(copy_board);
    }

    return false;
  }
  return false;
}

vector<int> solve(const vector<vector<int>> &lists) {
  int N = (lists.size() + 1) / 2;
  int M = lists.size();
  vector<bool> used(M, false);
  vector<vector<int>> board(N, vector<int>(N, 0));
  assert(rec(N - 1, used, board, lists));
  assert(ans_row >= 0);
  vector<int> ret(N);
  if (ans_is_row)
    for (int i = 0; i < N; ++i) ret[i] = board[ans_row][i];
  else
    for (int i = 0; i < N; ++i) ret[i] = board[i][ans_row];
  return ret;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int testcase = 1; testcase <= T; ++testcase) {
    int N;
    cin >> N;
    vector<vector<int>> lists(2 * N - 1, vector<int>(N));
    for (int i = 0; i < 2 * N - 1; ++i)
      for (int j = 0; j < N; ++j) cin >> lists[i][j];
    vector<int> ans = solve(lists);
    cout << "Case #" << testcase << ":";
    for (const auto &a : ans) cout << " " << a;
    cout << endl;
  }
}