Facebook Hacker Cup 2016 Round 1 40: Boomerang Tournament
解法
bitDP
補集合のビットマスクを列挙する方法頭いい。
コード
// #define _GLIBCXX_DEBUG #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <string.h> using namespace std; typedef signed long long ll; #define ALL(a) a.begin(), a.end() #define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end()) vector<pair<int, int>> solve(const vector<vector<int>> &win) { int N = win.size(); vector<vector<bool>> dp((1 << N), vector<bool>(N, false)); for (int i = 0; i < N; ++i) { dp[1 << i][i] = true; } vector<int> ans(N, 1); for (int cnt = 1; cnt < N; cnt *= 2) { for (int part = 0; part < (1 << N); ++part) { if (__builtin_popcount(part) != cnt) continue; int remain = (1 << N) - 1 - part; int complement = remain; while (complement > 0) { if (__builtin_popcount(complement) == cnt) { for (int i = 0; i < N; ++i) if (dp[part][i]) for (int j = 0; j < N; ++j) if (dp[complement][j] && win[i][j]) { dp[part | complement][i] = true; ans[i] = cnt * 2; } } complement = ((complement - 1) & remain); } } } vector<pair<int, int>> ret(N); for (int i = 0; i < N; ++i) { int low = N / ans[i] / 2 + 1; int high = N / 2 + 1; bool lost = false; for (int j = 0; j < N; ++j) if (j != i && !win[i][j]) lost = true; if (!lost) high = 1; ret[i] = {low, high}; } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); std::random_device rnd; std::mt19937 mt(rnd()); int T; cin >> T; for (int i = 0; i < T; ++i) { int N; cin >> N; vector<vector<int>> win(N, vector<int>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cin >> win[i][j]; } } vector<pair<int, int>> c = solve(win); cout << "Case #"; cout << (i + 1); cout << ": " << endl; for (auto p : c) { cout << p.first << " " << p.second << endl; } } }