結果

問題 No.1937 Various Tournament
ユーザー gew1fw
提出日時 2025-06-12 15:00:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,927 ms / 2,000 ms
コード長 1,707 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 87,368 KB
最終ジャッジ日時 2025-06-12 15:01:23
合計ジャッジ時間 59,638 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

sys.setrecursionlimit(1 << 25)

def main():
    import sys
    N = int(sys.stdin.readline())
    S = []
    for _ in range(N):
        S.append(list(map(int, sys.stdin.readline().split())))

    size = N
    log = size.bit_length() - 1

    @lru_cache(maxsize=None)
    def dp(mask):
        participants = [i for i in range(N) if (mask & (1 << i))]
        m = len(participants)
        if m == 1:
            return {participants[0]: 1}
        
        half = m // 2
        res = {}
        from itertools import combinations
        for left_indices in combinations(range(m), half):
            left = []
            right = []
            for i in range(m):
                if i in left_indices:
                    left.append(participants[i])
                else:
                    right.append(participants[i])
            left_mask = sum(1 << p for p in left)
            right_mask = sum(1 << p for p in right)
            left_dp = dp(left_mask)
            right_dp = dp(right_mask)
            
            for a in left_dp:
                for b in right_dp:
                    if S[a][b] == 1:
                        winner = a
                        ways = left_dp[a] * right_dp[b]
                    else:
                        winner = b
                        ways = left_dp[a] * right_dp[b]
                    if winner not in res:
                        res[winner] = 0
                    res[winner] += ways
        return res

    total = [0] * N
    for k in range(N):
        result = dp((1 << N) - 1)
        total[k] = result.get(k, 0)

    for k in range(N):
        print(total[k])

if __name__ == "__main__":
    main()
0