結果

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

ソースコード

diff # 

import sys
from itertools import combinations

def main():
    N = int(sys.stdin.readline())
    S = []
    for _ in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        S.append(row)
    
    participants = list(range(N))
    powers = []
    current = 1
    while current <= N:
        powers.append(current)
        current *= 2
    
    dp = {}
    for m in powers:
        for subset in combinations(participants, m):
            bitmask = 0
            for i in subset:
                bitmask |= 1 << i
            
            if m == 1:
                k = subset[0]
                dp[bitmask] = {k: 1}
            else:
                m_half = m // 2
                all_splits = list(combinations(subset, m_half))
                total = {}
                for a_group in all_splits:
                    b_group = tuple(x for x in subset if x not in a_group)
                    a_bitmask = 0
                    for x in a_group:
                        a_bitmask |= 1 << x
                    b_bitmask = 0
                    for x in b_group:
                        b_bitmask |= 1 << x
                    
                    if a_bitmask not in dp or b_bitmask not in dp:
                        continue
                    
                    a_dp = dp[a_bitmask]
                    b_dp = dp[b_bitmask]
                    
                    for a in a_group:
                        if a not in a_dp:
                            continue
                        for b in b_group:
                            if b not in b_dp:
                                continue
                            count_a = a_dp[a]
                            count_b = b_dp[b]
                            if count_a == 0 or count_b == 0:
                                continue
                            
                            if S[a][b] == 1:
                                winner = a
                            else:
                                winner = b
                            
                            if winner not in total:
                                total[winner] = 0
                            total[winner] += count_a * count_b
                dp[bitmask] = total
    
    full_bitmask = (1 << N) - 1
    result = dp.get(full_bitmask, {})
    
    for k in range(N):
        print(result.get(k, 0))

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