結果

問題 No.753 最強王者決定戦
ユーザー finefine
提出日時 2018-11-09 22:09:18
言語 C++14
(gcc 11.2.0 + boost 1.78.0)
結果
AC  
実行時間 283 ms / 1,000 ms
コード長 2,088 bytes
コンパイル時間 1,693 ms
使用メモリ 11,608 KB
最終ジャッジ日時 2022-12-26 20:05:40
合計ジャッジ時間 3,644 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 281 ms
11,532 KB
testcase_01 AC 281 ms
11,572 KB
testcase_02 AC 280 ms
11,516 KB
testcase_03 AC 283 ms
11,608 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