結果

問題 No.753 最強王者決定戦
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:58:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 716 ms / 1,000 ms
コード長 2,367 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 81,524 KB
最終ジャッジ日時 2025-04-09 20:59:49
合計ジャッジ時間 4,124 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from itertools import combinations

def main():
    a_table = []
    for _ in range(16):
        row = list(map(int, sys.stdin.readline().split()))
        a_table.append(row)
    
    # Precompute the winner table for 0-based indices
    win_table = [[0] * 16 for _ in range(16)]
    for i in range(16):
        for j in range(16):
            if i == j:
                win_table[i][j] = i  # Not used, just placeholder
                continue
            a = i + 1
            b = j + 1
            small = min(a, b)
            large = max(a, b)
            if a_table[small - 1][large - 1] == 1:
                winner = small
            else:
                winner = large
            # Convert back to 0-based
            win_table[i][j] = winner - 1
    
    memo = {}
    
    def dfs(mask):
        if mask in memo:
            return memo[mask]
        
        players = [i for i in range(16) if (mask & (1 << i))]
        n = len(players)
        if n == 1:
            res = [0] * 16
            res[players[0]] = 1
            memo[mask] = res
            return res
        
        half = n // 2
        res = [0] * 16
        
        # Generate all possible splits into left and right
        for left_players in combinations(players, half):
            left_mask = 0
            for p in left_players:
                left_mask |= (1 << p)
            right_mask = mask ^ left_mask
            
            left_counts = dfs(left_mask)
            right_counts = dfs(right_mask)
            
            # Iterate through all possible winners in left and right
            for a in players:
                if not (left_mask & (1 << a)):
                    continue
                cnt_a = left_counts[a]
                if cnt_a == 0:
                    continue
                for b in players:
                    if not (right_mask & (1 << b)):
                        continue
                    cnt_b = right_counts[b]
                    if cnt_b == 0:
                        continue
                    w = win_table[a][b]
                    res[w] += cnt_a * cnt_b
        
        memo[mask] = res
        return res
    
    # The full mask is all 16 fighters: 0xFFFF
    full_mask = (1 << 16) - 1
    result = dfs(full_mask)
    
    for count in result:
        print(count)

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