GCJ 2016 Round 1A B: Rank and File
解法
ある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; } }