結果

問題 No.1937 Various Tournament
ユーザー gew1fw
提出日時 2025-06-12 20:04:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,869 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 84,684 KB
最終ジャッジ日時 2025-06-12 20:11:55
合計ジャッジ時間 75,366 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 TLE * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    S = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        S.append(row)
        idx += N

    log_n = N.bit_length() - 1
    dp = {}

    # Initialize dp for single-element subsets
    for k in range(1, N+1):
        mask = 1 << (k-1)
        dp[mask] = {k: 1}

    for d in range(1, log_n + 1):
        size = 2 ** d
        # Generate all subsets of size 'size'
        for bits in combinations(range(N), size):
            mask = 0
            for bit in bits:
                mask |= 1 << bit
            dp[mask] = {k+1: 0 for k in bits}
            # Generate all possible splits into two equal halves
            for a_bits in combinations(bits, size // 2):
                a_list = list(a_bits)
                a_mask = 0
                for a in a_list:
                    a_mask |= 1 << a
                b_list = list(set(bits) - set(a_bits))
                b_mask = 0
                for b in b_list:
                    b_mask |= 1 << b
                # Iterate over all possible a and b
                for a in a_list:
                    for b in b_list:
                        if S[a][b] == 1:
                            winner = a + 1
                        else:
                            winner = b + 1
                        # Get the counts from A and B
                        count_a = dp[a_mask][a+1] if (a+1) in dp[a_mask] else 0
                        count_b = dp[b_mask][b+1] if (b+1) in dp[b_mask] else 0
                        if winner in dp[mask]:
                            dp[mask][winner] += count_a * count_b

    full_mask = (1 << N) - 1
    for k in range(1, N+1):
        print(dp[full_mask].get(k, 0))

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