概要

企業を表す \(N\) 個の要素を円環上に並べ替え、隣接する企業同士の集客効果の合計を最大化する問題。ただし、最大 \(K\) 回のスワップ操作しか行えない。

考察

この問題は、円環上に並んだ企業の配置を並び替えて、隣接する企業同士の集客効果 \(C_{i,j}\) の合計を最大化するものです。制約として、最大 \(K\) 回の「2つの企業のブースを入れ替える」操作が可能です。

重要な観察

• \(N\) が非常に小さい（最大8）ため、すべての配置（順列）を全探索することが可能です。
• 各配置に対して、必要な最小スワップ回数を計算し、それが \(K\) 以下であれば候補となります。
• 円形であるため、隣接関係は \(i\) 番目と \((i+1) \bmod N\) 番目です。

素朴なアプローチの問題点

• 単純にランダムにスワップして評価しても、最適解にたどり着けない可能性があります。
• 探索範囲が広すぎると計算時間が爆発しますが、今回は \(N \leq 8\) なので、全順列（最大 \(8! = 40320\)）を試すことが現実的です。

解決方法

• すべての順列を生成し、それぞれについて「初期状態 \([0,1,\dots,N-1]\) からその順列を作るのに必要な最小スワップ回数」を計算します。
• そのスワップ回数が \(K\) 以下であれば、その配置による集客効果の合計を計算し、最大値を更新します。

アルゴリズム

1. 入力から \(N\), \(K\), 集客効果行列 \(C\) を読み込みます。
2. 初期状態の企業配置（\([0, 1, ..., N-1]\)）を用意します。
3. すべての順列（itertools.permutations）を生成します。
4. 各順列に対して：
   • 初期状態からその順列を作るのに必要な最小スワップ回数を計算します。
     • これは、順列を巡回置換に分解し、各巡回のサイズから求められます（巡回内の要素数 - 1 の合計）。
   • スワップ回数が \(K\) 以下であれば、その配置の集客効果の合計を計算します。
     • 円環なので、隣接ペアは \((i, (i+1)\bmod N)\) です。
   • 最大値を更新します。
5. 最終的な最大値を出力します。

例

例えば \(N=4\), \(K=2\), 配置が [1, 0, 2, 3] なら：

• 初期状態: [0, 1, 2, 3]
• この順列を得るには、0と1をスワップするだけで良いので、スワップ回数は1。
• よって、\(K=2\) 以下なので候補になります。

計算量

• 順列の個数：\(N!\)

• 各順列に対してスワップ回数とコストを計算するのに \(O(N)\)

• よって、

• 時間計算量: \(O(N! \cdot N)\)

• 空間計算量: \(O(N^2)\) （集客効果行列の保存）

\(N \leq 8\) なので、最大でも約 \(40320 \times 8 = 322560\) 回程度の計算となり、十分高速です。

実装のポイント

• permutations を使って全順列を生成するのが鍵。
• 最小スワップ回数は、順列を巡回に分解して求めることで正確に計算できます。
• 隣接関係は円環を意識して \((i+1) \bmod N\) で処理しましょう。
• 企業番号は0-indexedで扱うことで、リストのインデックスと一致させると実装が楽です。

ソースコード

from itertools import permutations

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    C = []
    idx = 2
    for i in range(N):
        row = list(map(int, data[idx:idx+N]))
        C.append(row)
        idx += N
    
    # 初期状態での隣接ペアのコスト合計を計算する関数
    def calculate_cost(perm):
        cost = 0
        for i in range(N):
            a = perm[i]
            b = perm[(i+1) % N]
            cost += C[a][b]
        return cost
    
    # 現在の配置（0-indexed）
    initial = list(range(N))
    
    max_cost = 0
    
    # 全ての順列を試す
    for perm in permutations(initial):
        # swap回数を計算
        # 順列の転倒数などを正確に数えるのは大変なので、
        # 順列間の最小swap回数 = ハミング距離的なものではなく、
        # 実際には隣接swapでの最小交換回数（バブルソートのswap数） = 転倒数
        # だが、ここでは全置換に対してswap回数を直接計算する
        
        # しかし、N<=8なので、順列のswap距離を正確に計算しても間に合う
        # 最小swap回数を求めるには、初期 [0,1,2,...,N-1] から perm への最小swap回数
        # これは、置換を巡回ごとに分解し、各巡回の長さ-1の和
        
        def min_swaps_to_transform(src, tgt):
            # srcをtgtにするのに必要な最小swap回数
            # tgt_perm[i] = tgt.index(i)
            # src_perm[i] = src.index(i)
            # つまり、src_perm[tgt[i]] = pos in src of element tgt[i]
            # 実際には、srcが[0,1,...,N-1]なら、tgt_perm[i] = tgt[i]の位置
            # つまり、target permutation が perm なら、そのswap回数を求めればよい
            
            # target permutation が perm (0-based)のときの最小swap回数
            visited = [False]*N
            swaps = 0
            for i in range(N):
                if visited[i] or perm[i] == i:
                    continue
                cycle_size = 0
                x = i
                while not visited[x]:
                    visited[x] = True
                    x = perm[x]
                    cycle_size += 1
                if cycle_size > 0:
                    swaps += cycle_size - 1
            return swaps
        
        swaps_needed = min_swaps_to_transform(initial, perm)
        if swaps_needed <= K:
            cost = calculate_cost(perm)
            if cost > max_cost:
                max_cost = cost
                
    print(max_cost)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。