概要

\(N\) 個のブースを円形に並べるとき、隣接するブース間の集客効果の合計を最大化する問題です。初期状態から最大 \(K\) 回の「2つの企業の入れ替え」操作が許されています。

考察

この問題を解くための重要なポイントは以下の2点です。

1. 制約の小ささに注目する 企業の数 \(N\) が最大で \(8\) と非常に小さいです。\(N\) 個の要素の並べ替え（順列）の総数は \(N!\) 通りであり、\(8! = 40,320\) 通りしかありません。これなら、すべての並び方を全探索することが可能です。

2. 最小交換回数の計算 ある並び（順列）を実現するために必要な最小の交換回数は、「要素数 \(N\) - 置換のサイクル数」で求められます。 例えば、初期状態 \((1, 2, 3, 4)\) から \((2, 3, 1, 4)\) にしたい場合：

   • \(1 \to 2 \to 3 \to 1\) （長さ3のサイクル）
   • \(4 \to 4\) （長さ1のサイクル） サイクル数は 2 なので、最小交換回数は \(4 - 2 = 2\) 回となります。 この回数が \(K\) 以下であれば、その並び方は実現可能です。

アルゴリズム

以下の手順で解を求めます。

1. 全順列の生成: \(0\) から \(N-1\) までの数字の順列 \(P\) をすべて生成します。各順列 \(P\) は、「ブース \(i\) に企業 \(P_i\) がいる」状態を表します。
2. 最小交換回数の判定: 各順列について、初期状態 \((0, 1, \dots, N-1)\) からその状態にするための最小交換回数を計算します。
   • 未訪問の要素から辿り、サイクルを分解して個数をカウントします。
   • \(N - (\text{サイクル数}) \leq K\) であるかを確認します。
3. 集客効果の計算: 条件を満たす順列について、円形に並んだ隣接ペアの集客効果を合計します。
   • 隣接ペアは \((P_0, P_1), (P_1, P_2), \dots, (P_{N-2}, P_{N-1})\) および、円形なので \((P_{N-1}, P_0)\) です。
4. 最大値の更新: 計算した合計値の最大値を保持し、最後にそれを出力します。

計算量

• 時間計算量: \(O(N \cdot N!)\)
  • 順列の総数が \(N!\) 通り。
  • 各順列に対して、サイクルの計算と集客効果の合計算出に \(O(N)\) かかります。
  • \(N=8\) のとき \(8 \times 40,320 \approx 3.2 \times 10^5\) となり、制限時間内に十分間に合います。
• 空間計算量: \(O(N^2)\)
  • 集客効果の行列 \(C\) を保持するために \(N \times N\) のメモリを使用します。

実装のポイント

• サイクルのカウント: visited 配列を用意して、一度探索した要素を記録しながらループを回すことで、効率的にサイクル数を数えることができます。
• 円環の処理: 最後に \(P_{N-1}\) と \(P_0\) の隣接分を加算するのを忘れないようにしましょう。
• Pythonの活用: itertools.permutations を使うと、全順列を簡単に列挙できます。

ソースコード

import sys
from itertools import permutations

def solve():
    """
    The problem asks for the maximum sum of collection effects between adjacent companies
    in a circular arrangement of N booths, starting from an initial configuration and 
    performing at most K swaps.
    
    Constraints:
    N is small (3 to 8), so we can iterate through all N! permutations.
    The number of swaps to transform the initial state (1, 2, ..., N) to a target
    permutation P is given by N - (number of cycles in P).
    
    Complexity:
    N! is at most 8! = 40,320.
    For each permutation, cycle counting and effect summation take O(N).
    Total complexity: O(N * N!), which is approximately 3.2e5 operations.
    This is well within the time limit for Python 3.
    """
    
    # Read all input data at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # First two values are N (number of companies) and K (max swap operations)
    N = int(input_data[0])
    K = int(input_data[1])
    
    # The next N*N values form the collection effect matrix C
    # C[i][j] represents the effect between company i+1 and company j+1
    C = []
    for i in range(N):
        # Extract the i-th row of the matrix
        row = [int(x) for x in input_data[2 + i * N : 2 + (i + 1) * N]]
        C.append(row)
        
    max_effect = -1
    
    # Iterate through all possible permutations of companies (0-indexed)
    # Each permutation p represents company p[i] being placed at booth i+1
    for p in permutations(range(N)):
        # Calculate the minimum number of swaps needed to reach permutation p
        # from the identity permutation (0, 1, ..., N-1).
        # This is equal to N - (number of disjoint cycles in the permutation).
        visited = [False] * N
        cycles = 0
        for i in range(N):
            if visited[i]:
                continue
            cycles += 1
            curr = i
            while not visited[curr]:
                visited[curr] = True
                curr = p[curr]
        
        min_swaps = N - cycles
        
        # If the permutation is reachable within K swaps, calculate its total effect
        if min_swaps <= K:
            # The booths are arranged in a circle: 1-2, 2-3, ..., (N-1)-N, N-1
            # In 0-indexing: (0,1), (1,2), ..., (N-2, N-1), (N-1, 0)
            current_effect = 0
            for i in range(N - 1):
                # Effect between company at booth i and company at booth i+1
                current_effect += C[p[i]][p[i+1]]
            # Effect between company at booth N and company at booth 1
            current_effect += C[p[N-1]][p[0]]
            
            # Keep track of the maximum effect found so far
            if current_effect > max_effect:
                max_effect = current_effect
                
    # Output the maximum achieved sum of collection effects
    print(max_effect)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。