Facebook Hacker Cup 2016 Round 1 Boomerang Tournament
解法
制約が 2^K となっていますが, この制約により, この問題のトーナメント方式は, 普通のトーナメント方式と同じであることがわかります(下図)。
そうすると, 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; }