mayoko’s diary

プロコンとかいろいろ。

Facebook Hacker Cup 2016 Round 1 Boomerang Tournament

解法

制約が 2^K となっていますが, この制約により, この問題のトーナメント方式は, 普通のトーナメント方式と同じであることがわかります(下図)。
f:id:mayokoex:20160118090057p:plain

そうすると, dp[state][i] = (選手 i が, 状態 state の集団で優勝することはあり得るか) という dp を考えることが出来ます。

state が, 0100 のように一人だけの時は 1 の bit が立ってる人が優勝します。一般の場合は, state で立っている bit の数を半分ずつに分割して (state = sub | xsub とする), それぞれの分割で優勝する可能性があるときは, sub で優勝する人 a と xsub で優勝する人 b を勝負させて, a が勝つ場合は dp[state][a] = true, そうでない場合は dp[state][b] = true とわかります。

あり得る順位は, この方式が普通のトーナメント方式と同じことを考えると, n 人の中で負ける可能性がある場合は, N/n + 1 位を撮る可能性がある, ということなのでこれを考慮してがんばります。

int W[20][20];
int dp[1<<18][18];
int N;

void dfs(int s, int n, vector<set<int> >& S) {
    if (dp[s][0] >= 0) return;
    if (n == 1) {
        for (int i = 0; i < N; i++) {
            if ((s>>i)&1) dp[s][i] = 1;
            else dp[s][i] = 0;
        }
        return;
    }
    for (int i = 0; i < N; i++) dp[s][i] = 0;
    int sub = s;
    do {
        if (__builtin_popcount(sub) == n/2) {
            dfs(sub, n/2, S);
            int xsub = s^sub;
            dfs(xsub, n/2, S);
            for (int i = 0; i < N; i++) {
                if ((sub>>i&1) == 1 && dp[sub][i] == 1) {
                    for (int j = 0; j < N; j++) {
                        if ((xsub>>j&1) == 1 && dp[xsub][j] == 1) {
                            if (W[i][j]) {
                                dp[s][i] = 1;
                                if (n==N) S[i].insert(1);
                                S[j].insert(N/n+1);
                            } else {
                                dp[s][j] = 1;
                                if (n==N) S[j].insert(1);
                                S[i].insert(N/n+1);
                            }
                        }
                    }
                }
            }
        }
        sub = (sub-1) & s;
    } while (sub != s);
}

void solve(int T) {
    cin >> N;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> W[i][j];
    if (N == 1) {
        cout << "Case #" << T << ": " << endl;
        cout << 1 << " " << 1 << endl;
        return;
    }
    vector<set<int> > S(N);
    memset(dp, -1, sizeof(dp));
    dfs((1<<N)-1, N, S);
    cout << "Case #" << T << ": " << endl;
    for (int i = 0; i < N; i++) {
        int mini = 100, maxi = -100;
        for (auto it = S[i].begin(); it != S[i].end(); it++) {
            mini = min(mini, *it);
            maxi = max(maxi, *it);
        }
        cout << mini << " " << maxi << endl;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}