Facebook Hacker Cup 2016 Round 1 Boomerang Tournament

,

set dpを思い付くまでかなり時間がかかってしまった。

Boomerang Tournament

解法

bit DP。 $S$に含まれる参加者でトーナメントをしたときに優勝できる参加者の集合を$T$として、${\rm dp}_S = T$。

最低順位に関しては、対戦して負ける相手がいるかいないかのみ見ればよい。

実装

サイズ$k$の部分集合を列挙するテク(蟻本p143)があるようなので、それを使うべき。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
void solve() {
    int n; cin >> n;
    vector<uint16_t> w(n);
    repeat (y,n) repeat (x,n) { int z; cin >> z; if (z) w[y] |= 1<<x; }
    vector<uint16_t> dp(1<<n); // dp[s]&(1<<y) means that y can win log|s| times when s are used
    repeat (s, 1<<n) {
        int popcnt = __builtin_popcount(s);
        if (__builtin_popcount(popcnt) != 1) continue;
        if (popcnt == 1) {
            dp[s] = s;
        } else {
            repeat (t,1<<n) if ((t & s) == t and __builtin_popcount(t) == (popcnt >> 1)) {
                int u = s & ~t;
                repeat (y,n) if (dp[t] & (1<<y) and dp[u] & w[y]) {
                    dp[s] |= 1<<y;
                }
            }
        }
    }
    repeat (y,n) {
        int popcnt = 0;
        repeat (s, 1<<n) if (dp[s] & (1<<y)) popcnt = max(popcnt, __builtin_popcount(s));
        int best = (n/popcnt)/2+1;
        int worst = __builtin_popcount(w[y]) == n-1 ? 1 : n/2+1;
        cout << best << ' ' << worst << endl;
    }
}
int main() {
    int testcases; cin >> testcases;
    repeat (testcase, testcases) {
        cout << "Case #" << testcase+1 << ": " << endl;
        solve();
    }
    return 0;
}