結果

問題 No.1937 Various Tournament
ユーザー gew1fw
提出日時 2025-06-12 19:58:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,018 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 91,684 KB
最終ジャッジ日時 2025-06-12 20:01:03
合計ジャッジ時間 3,888 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    S = []
    for _ in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        S.append(row)
    
    full_mask = (1 << N) - 1
    dp = [{} for _ in range(1 << N)]
    
    for mask in range(1 << N):
        size = bin(mask).count('1')
        if size == 0 or (size & (size - 1)) != 0:
            continue  # Not a power of two
        
        participants = [i for i in range(N) if (mask & (1 << i))]
        for r in participants:
            if size == 1:
                dp[mask][r] = 1
            else:
                half = size // 2
                total = 0
                # Generate all possible a_masks of size half
                for indices in combinations(range(len(participants)), half):
                    a_participants = [participants[i] for i in indices]
                    a_mask = 0
                    for p in a_participants:
                        a_mask |= (1 << p)
                    if (a_mask & mask) != a_mask:
                        continue  # Not a subset
                    if bin(a_mask).count('1') != half:
                        continue
                    b_mask = mask ^ a_mask
                    # Check if r is in a_participants
                    if r in a_participants:
                        a_winner = r
                        if a_winner not in dp[a_mask]:
                            continue
                        ways_A = dp[a_mask][a_winner]
                        if ways_A == 0:
                            continue
                        # Sum over b in B where S[a_winner][b] == 1
                        sum_b = 0
                        for b in participants:
                            if not (b_mask & (1 << b)):
                                continue
                            if S[a_winner][b] == 1:
                                if b in dp[b_mask]:
                                    sum_b += dp[b_mask][b]
                        contribution = ways_A * sum_b
                        total += contribution
                    else:
                        b_winner = r
                        if b_winner not in dp[b_mask]:
                            continue
                        ways_B = dp[b_mask][b_winner]
                        if ways_B == 0:
                            continue
                        sum_a = 0
                        for a in participants:
                            if not (a_mask & (1 << a)):
                                continue
                            if S[b_winner][a] == 1:
                                if a in dp[a_mask]:
                                    sum_a += dp[a_mask][a]
                        contribution = sum_a * ways_B
                        total += contribution
                dp[mask][r] = total
    
    for k in range(N):
        print(dp[full_mask].get(k, 0))
    
if __name__ == "__main__":
    main()
0