[アルゴリズム]白準開始とリンク(14889回)Python

コンポジット
nの範囲は最大20である.
そのためO(n^3)もタイムアウトしていません.

My solution

from itertools import combinations, permutations

# Calculate diff of teamA and teamB
def calculate(teamA, teamB):
    global stats
    sumA = 0
    sumB = 0
    memsA = permutations(teamA, 2)
    memsB = permutations(teamB, 2)

    for memA in memsA:
        sumA += stats[memA[0]][memA[1]]
    for memB in memsB:
        sumB += stats[memB[0]][memB[1]]

    result = abs(sumA - sumB)

    return result

# Initialize values
answer = 0
n = int(input())
stats = [[0 for j in range(n)] for i in range(n)]

# Input values
for i in range(n):
    stats[i] = list(map(int, input().split()))

# Deside members of team A, B for combination
teamA = list(combinations(range(n), int(n/2)))
for idx in range(len(teamA)):
    teamB = [k for k in range(n) if k not in teamA[idx]]
    tmp = calculate(teamA[idx], teamB)
    if idx == 0:
        answer = tmp
    elif tmp < answer:
        answer = tmp

print(answer)

補足すべき点

の組み合わせによって各グループのメンバーが決定され、再びメンバーの2名が順番にペアリングされる.

計算関数の時間複雑度はO(n^2)であった.

とは逆に、より簡単な実装方法がある.

teama,Bが決まると2(1人あたり2名)で、ドアで値上げします.

もちろん同じ時間複雑度はO(N^2)ですが、コードは簡単になります.

時間の複雑さを低減するためにdfsを用いることができる.

補足コード

from itertools import combinations, permutations


# Initialize values
answer = 0
n = int(input())
stats = [[0 for j in range(n)] for i in range(n)]

# Input values
for i in range(n):
    stats[i] = list(map(int, input().split()))

# Deside members of team A, B for combination
teamA = list(combinations(range(n), int(n/2)))
for idx in range(len(teamA)):
    sumA = 0
    sumB = 0
    teamB = [k for k in range(n) if k not in teamA[idx]]
    # Find sumA, sumB and diff
    for x in teamA[idx]:
        for y in teamA[idx]:
            if x != y:
                sumA += stats[x][y]
    for x in teamB:
        for y in teamB:
            if x != y:
                sumB += stats[x][y]

    tmp = abs(sumA - sumB)

    # Find min value
    if idx == 0:
        answer = tmp
    elif tmp < answer:
        answer = tmp

print(answer)

奥応?!長さは短くなりましたが、もっと時間がかかります…?ライブラリの方が効率的なようですね