結果

問題 No.1937 Various Tournament
ユーザー qwewe
提出日時 2025-05-14 13:21:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 625 ms / 2,000 ms
コード長 3,929 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 88,352 KB
最終ジャッジ日時 2025-05-14 13:24:24
合計ジャッジ時間 20,195 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections
import itertools

def solve():
    N = int(input())
    S_matrix = []
    for _ in range(N):
        S_matrix.append(list(map(int, input().split())))

    # dp[mask] is a dictionary mapping winner_player_id (1-indexed) to count_of_permutations.
    # mask bits are 0-indexed: bit i corresponds to player i+1.
    dp = [collections.defaultdict(int) for _ in range(1 << N)]

    # Base cases: masks representing a single player.
    # If player (i+1) is the only one, they win in 1 way (permutation is just [player i+1]).
    for i in range(N):  # i is the 0-indexed bit position
        player_id = i + 1
        mask = 1 << i
        dp[mask][player_id] = 1

    # Iterate m = size of player set (popcount of mask).
    # m must be a power of 2: 2, 4, 8, ..., N.
    current_m = 2
    while current_m <= N:
        for current_mask_val in range(1 << N):
            # Only process masks with popcount equal to current_m.
            # Using int.bit_count() if Python 3.10+, else bin().count('1').
            # For compatibility, using bin().count('1').
            if bin(current_mask_val).count('1') != current_m:
                continue

            # Identify players (their 0-indexed bit positions) present in current_mask_val.
            players_in_current_mask_bits = []
            for i in range(N):
                if (current_mask_val >> i) & 1:
                    players_in_current_mask_bits.append(i)
            
            # Split `current_m` players into two halves for sub-tournaments.
            # `num_players_in_half` players for the "left half" permutation.
            # Remaining players for the "right half" permutation.
            num_players_in_half = current_m // 2
            
            # Iterate over all ways to choose `num_players_in_half` players (by bit positions)
            # from `players_in_current_mask_bits` to form `submask1`.
            for chosen_bits_for_submask1 in itertools.combinations(players_in_current_mask_bits, num_players_in_half):
                submask1_val = 0
                for bit_pos in chosen_bits_for_submask1:
                    submask1_val |= (1 << bit_pos)
                
                # Remaining players from current_mask_val form submask2_val.
                submask2_val = current_mask_val ^ submask1_val

                # Retrieve pre-computed results for these two submasks.
                left_half_results = dp[submask1_val]   # {winner_L_id: count_L_perms}
                right_half_results = dp[submask2_val] # {winner_R_id: count_R_perms}

                # Combine results:
                # For each pair of (winner_L from left_half, winner_R from right_half).
                for winner_L_id, num_perms_L in left_half_results.items():
                    for winner_R_id, num_perms_R in right_half_results.items():
                        # Simulate the match between winner_L and winner_R.
                        # S_matrix is 0-indexed, so use player_id - 1.
                        if S_matrix[winner_L_id - 1][winner_R_id - 1] == 1: # winner_L beats winner_R
                            # Overall winner for permutations formed this way is winner_L.
                            # Number of such permutations = num_perms_L * num_perms_R.
                            dp[current_mask_val][winner_L_id] += num_perms_L * num_perms_R
                        else: # winner_R beats winner_L
                            dp[current_mask_val][winner_R_id] += num_perms_L * num_perms_R
        
        if current_m == N: # All masks of size N (i.e., the full set) have been processed.
            break 
        current_m *= 2 # Next power of 2 for m.

    # Final answers are in dp[(1<<N) - 1].
    final_full_mask_val = (1 << N) - 1
    results_for_full_tournament = dp[final_full_mask_val]

    for player_id_to_print in range(1, N + 1):
        print(results_for_full_tournament[player_id_to_print])

solve()
0