概要

最初の配置（企業 \(i\) がブース \(i\)）から、交換回数が \(K\) 回以下で到達できる配置のうち、円環で隣り合うペアの効果合計を最大化します。
\(N \le 8\) なので、全ての配置（順列）を試し、到達可能かどうかを「必要最小交換回数」で判定します。

考察

重要な気づき1：配置は「順列」で表せる

最終的な配置を、長さ \(N\) の配列（順列）\(p\) で

• \(p[i] =\) ブース \(i\) にいる企業番号
  

と表せます（コードでは 0-index）。

このとき、隣接ペアの合計は円環なので \(\sum_{i=0}^{N-1} C_{p[i],\,p[(i+1)\bmod N]}\) で計算できます。

重要な気づき2：「交換回数 \(K\) 以下で到達可能か」は最小交換回数で判定できる

操作は「任意の2社の交換」＝配列の2要素の swap です。
ある順列 \(p\) を初期配置（恒等順列 \([0,1,2,\dots]\)）から作るのに必要な最小 swap 回数は次で求まります：

• 順列 \(p\) を写像 \(i \to p[i]\) とみなし、サイクル分解する
• サイクル数を cycles とすると、最小 swap 回数は [ \text{dist} = N - \text{cycles} ]

例：\(N=4\), \(p=[1,0,3,2]\)
サイクルは \((0\,1)(2\,3)\) で cycles=2、よって dist = 4-2 = 2。実際に 2 回 swap で作れます。

したがって、各配置 \(p\) について dist <= K なら到達可能、そうでなければ不可能です。

素朴に「最大 \(K\) 回 swap を全探索」すると厳しい

swap の選び方は各手で \(\binom{N}{2}\) 通りあり、深さ \(K\) の探索は爆発します。
一方で \(N \le 8\) なら 全順列は最大でも \(8! = 40320\) 個なので、「全配置を列挙して、到達可能かを数学的に判定」するのが簡単かつ確実です。

アルゴリズム

1. 全ての順列 \(p\)（ブースへの企業配置）を列挙する。
2. その順列のサイクル数 cycles を、visited 配列で数える（未訪問から辿って1サイクル）。
3. dist = N - cycles を計算し、dist > K ならこの配置はスキップ。
4. dist <= K なら、円環の隣接ペア [ (p[0],p[1]), (p[1],p[2]), \dots, (p[N-1],p[0]) ] の合計を計算し、最大値を更新する。
5. 最大値を出力。

計算量

• 時間計算量: \(O(N! \cdot N)\)
  （各順列ごとにサイクル計算 \(O(N)\) ＋ スコア計算 \(O(N)\)）
• 空間計算量: \(O(N^2)\)
  （効果行列 \(C\) が支配的。ほかに visited など \(O(N)\)）

実装のポイント

• 順列 perm は「ブース \(i\) にいる企業」を表すように扱う（コードの a=perm[i] など）。
• サイクル数は visited を使って、j = perm[j] と辿ることで数えられる。
• 円環なので隣は (i+1) % N を使う（最後と最初が隣接）。

ソースコード

import sys
from itertools import permutations

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    C = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for perm in permutations(range(N)):
        visited = [False] * N
        cycles = 0
        for i in range(N):
            if not visited[i]:
                cycles += 1
                j = i
                while not visited[j]:
                    visited[j] = True
                    j = perm[j]
        dist = N - cycles
        if dist > K:
            continue

        s = 0
        for i in range(N):
            a = perm[i]
            b = perm[(i + 1) % N]
            s += C[a][b]
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。