概要

円形に並んだ \(N\) 個のブースに \(N\) 社を配置し、隣接ペアの集客効果の合計を最大化する問題です。初期配置からの入れ替え操作回数が \(K\) 回以下という制約のもとで、最適な配置を求めます。

考察

重要な気づき①：\(N\) が非常に小さい

\(N \leq 8\) なので、全ての並べ方（順列）を列挙しても \(8! = 40320\) 通りしかありません。これは十分高速に処理できます。

重要な気づき②：スワップ回数と順列の関係

初期配置は企業 \(i\) がブース \(i\) にいる状態、つまり恒等置換 \((0, 1, 2, \ldots, N-1)\) です。ある順列 \(p\) に到達するために必要な最小スワップ回数は、置換の理論から次の公式で求められます：

\[\text{最小スワップ回数} = N - (\text{順列 } p \text{ のサイクル数})\]

具体例：\(N = 4\) で順列 \(p = (1, 0, 3, 2)\) を考えます。 - サイクル分解：\((0 \leftrightarrow 1)(2 \leftrightarrow 3)\) → サイクル数 \(= 2\) - 最小スワップ回数 \(= 4 - 2 = 2\)（企業0と1を交換、企業2と3を交換）

恒等置換はサイクル数が \(N\) なのでスワップ回数は \(0\)、一つの巨大サイクルだとスワップ回数は \(N-1\) になります。

解法の方針

全順列を列挙し、各順列について： 1. 最小スワップ回数が \(K\) 以下かチェック 2. 条件を満たすなら、隣接ペアの集客効果の合計を計算 3. その最大値を答えとする

アルゴリズム

1. 入力を読み取る。
2. \(N!\) 通りの全順列を列挙する。
3. 各順列 \(p\) に対して：
   • サイクル分解を行い、サイクル数を数える。
   • \(N - \text{サイクル数} \leq K\) ならば、その順列は \(K\) 回以下のスワップで到達可能。
   • 到達可能な場合、円形に隣接する全ペアのスコア \(\sum_{i=0}^{N-1} C_{p[i]}[p[(i+1) \bmod N]]\) を計算する。
4. スコアの最大値を出力する。

サイクル数の計算方法

順列を有向グラフとみなし、\(i \to p[i]\) の辺をたどります。未訪問の頂点から出発し、元に戻るまでたどると1つのサイクルが見つかります。これを全頂点について繰り返してサイクル数を数えます。

計算量

• 時間計算量: \(O(N! \cdot N)\)
  • 全順列の列挙に \(O(N!)\)、各順列に対するサイクル数計算とスコア計算にそれぞれ \(O(N)\)
  • \(N \leq 8\) のとき \(8! \times 8 = 322560\) で十分高速
• 空間計算量: \(O(N^2)\)
  • 集客効果の行列 \(C\) の格納に \(O(N^2)\)

実装のポイント

• 企業番号を 0-indexed で扱うと、順列やインデックス操作がシンプルになります。
• 円形配置なので、ブース \(i\) の隣はブース \((i+1) \bmod N\) です。ブース \(N-1\) とブース \(0\) の隣接を忘れないように注意しましょう。
• 「最小スワップ回数 \(= N - \text{サイクル数}\)」という公式は置換群の基本的な性質です。長さ \(L\) のサイクルを恒等置換に戻すには \(L-1\) 回のスワップが必要で、全サイクルの合計が \(\sum (L_i - 1) = N - \text{サイクル数}\) となることから導かれます。

ソースコード

from itertools import permutations

def solve():
    N, K = map(int, input().split())
    C = []
    for _ in range(N):
        C.append(list(map(int, input().split())))
    
    # Initial permutation is (0, 1, 2, ..., N-1) representing enterprise i at booth i
    # We need to find a permutation of enterprises placed in booths 1..N (circular)
    # such that the sum of C[perm[i]][perm[(i+1)%N]] is maximized
    # and the permutation can be reached from identity in at most K swaps.
    
    # The minimum number of swaps to go from identity to a permutation p is N - (number of cycles in p).
    
    def cycle_count(perm):
        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]
        return cycles
    
    def score(perm):
        s = 0
        for i in range(N):
            s += C[perm[i]][perm[(i + 1) % N]]
        return s
    
    best = 0
    for perm in permutations(range(N)):
        swaps_needed = N - cycle_count(perm)
        if swaps_needed <= K:
            s = score(perm)
            if s > best:
                best = s
    
    print(best)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。