結果

問題 No.753 最強王者決定戦
ユーザー finefine
提出日時 2018-11-09 22:09:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 295 ms / 1,000 ms
コード長 2,088 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 171,620 KB
実行使用メモリ 11,788 KB
最終ジャッジ日時 2024-11-21 05:59:45
合計ジャッジ時間 3,508 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 292 ms
11,788 KB
testcase_01 AC 292 ms
11,768 KB
testcase_02 AC 295 ms
11,620 KB
testcase_03 AC 295 ms
11,636 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll dp[1 << 16][16];
int a[16][16];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            cin >> a[i][j];
        }
    }

    vector< vector<int> > memo(17);
    for (int i = 1; i < (1 << 16); i++) {
        int cnt = __builtin_popcount(i);
        memo[cnt].push_back(i);
    }

    for (int i = 0; i < 16; i++) {
        dp[1 << i][i] = 1;
    }

    for (int cnt : {1, 2, 4}) {
        for (int i : memo[cnt]) {
            for (int j : memo[cnt]) {
                if (i & j) continue;
                for (int k = 0; k < 16; k++) {
                    if (i & (1 << k)) {
                        for (int l = 0; l < 16; l++) {
                            if (j & (1 << l)) {
                                int winner;
                                if (k < l) {
                                    winner = (a[k][l] == 1 ? k : l); 
                                } else {
                                    winner = (a[l][k] == 1 ? l : k); 
                                }
                                dp[(i | j)][winner] += dp[i][k] * dp[j][l];
                            }
                        }
                    }
                }
            }
        }
    }

    for (int i : memo[8]) {
        int j = (1 << 16) - 1;
        j ^= i;
        for (int k = 0; k < 16; k++) {
            if (i & (1 << k)) {
                for (int l = 0; l < 16; l++) {
                    if (j & (1 << l)) {
                        int winner;
                        if (k < l) {
                            winner = (a[k][l] == 1 ? k : l); 
                        } else {
                            winner = (a[l][k] == 1 ? l : k); 
                        }
                        dp[(i | j)][winner] += dp[i][k] * dp[j][l];
                    }
                }
            }
        }     
    }

    for (int i = 0; i < 16; i++) {
        cout << dp[(1 << 16) - 1][i] << endl;
    }
    return 0;
}
0