概要

\(N\)人の社員の発表順を決め、総合スコア（各社員のプレゼン力と発表順の積の合計）を最大化する問題です。ただし、\(M\)個の「社員\(U\)が社員\(V\)より先に発表する」という制約条件を満たす必要があります。

考察

問題の制約条件では\(N \leq 8\)と非常に小さいため、すべての可能な発表順（順列）を列挙して制約条件をチェックし、総合スコアを計算する全探索アプローチが有効です。\(N=8\)の場合の順列の総数は\(8! = 40320\)通りであり、これは十分に扱える範囲です。各順列に対して\(M\)個の制約条件をチェックするため、全体として\(O(N! \times M)\)の計算量になりますが、\(M\)も最大で28個程度なので現実的な時間で計算できます。

アルゴリズム

1. すべての可能な発表順（\(1\)から\(N\)までの順列）を生成する
2. 各順列について、与えられた全ての制約条件を満たすかチェックする
   • 各制約条件\((U, V)\)について、順列中で\(U\)の位置が\(V\)の位置より前にあるかを確認
3. 制約条件を満たす順列について、総合スコア\(\sum_{i=1}^{N} A_i \times P_i\)を計算する
4. 得られた総合スコアの最大値を出力する

計算量

• 時間計算量: \(O(N! \times M \times N)\)
  • 順列の数: \(N!\)
  • 各順列に対する制約チェック: \(M\)回（各チェックに\(O(N)\)のindex探索）
  • スコア計算: \(O(N)\)
• 空間計算量: \(O(N! \times N)\)
  • 全ての順列をメモリに保持する必要はなく、1つずつ処理するため実際には\(O(N)\)

実装のポイント

• Pythonのitertools.permutationsを使って全ての順列を効率的に生成

• 制約条件は0-indexedに変換して処理

• 各順列が制約を満たすかどうかをindexメソッドで位置を検索して確認

• 総合スコア計算時には、0-indexedの順序を1-indexedに変換（order+1）

• 最大スコアを更新しながら探索を進める

  ソースコード

import itertools

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    A = list(map(int, data[2:2+n]))
    constraints = []
    index = 2 + n
    for i in range(m):
        u = int(data[index]); v = int(data[index+1])
        constraints.append((u-1, v-1))  # 0-indexedに変換
        index += 2
        
    # すべての順列を生成
    all_permutations = itertools.permutations(range(n))
    best_score = -1
    
    for perm in all_permutations:
        # 順列permが制約を満たすかチェック
        valid = True
        for (u, v) in constraints:
            pos_u = perm.index(u)
            pos_v = perm.index(v)
            if pos_u >= pos_v:
                valid = False
                break
        if not valid:
            continue
            
        # 総合スコアを計算
        score = 0
        for order, person in enumerate(perm):
            # orderは0-indexedの順番。実際の発表順はorder+1
            score += A[person] * (order+1)
            
        if score > best_score:
            best_score = score
            
    print(best_score)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。