読者です 読者をやめる 読者になる 読者になる

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;
    }
  }
}