概要

社員の発表順を制約のもとで並び替えて、総合スコア \( \sum_{i=1}^{N} A_i \times P_i \) を最大化する問題です。

考察

まず、制約がない場合、総合スコアを最大化するには「プレゼン力 \(A_i\) が大きい社員ほど早く発表する（順位 \(P_i\) が小さい）」ように並べるのが最適です。これは直感的にも理解しやすく、例えば \(A = [3, 1, 2]\) であれば、発表順を \([3, 1, 2]\) → 順位 \([1, 2, 3]\) とすることでスコアが最大になります。

しかし今回は、いくつかの「社員 \(U_k\) は社員 \(V_k\) よりも先に発表しなければならない」という制約があります。このような関係は有向グラフで表現でき、さらにトポロジカルソートの考え方と関連しています。制約を満たしつつ最適な順列を探す必要があります。

素朴な方法として考えられるのは、すべての順列を試すことです。しかし、\(N\) が最大8であるため、全順列の数は最大でも \(8! = 40320\) 通りであり、十分高速に処理可能です。したがって、全探索による解法が現実的かつ安全です。

この方針では： 1. すべての順列を生成する。 2. 各順列について、制約をすべて満たしているかを確認する。 3. 満たしていればスコアを計算し、最大値を更新する。

これにより、正しい答えを得ることができます。

アルゴリズム

1. 入力を受け取り、制約をリストに格納（ただし、0-indexedにする）。
2. Pythonの itertools.permutations を使い、社員のすべての発表順序（順列）を生成。
3. 各順列に対して以下を行う：
   • 制約リスト内のすべての条件 \((u, v)\) について、順列内で \(u\) が \(v\) より前に来ているかをチェック。
   • 一つでも違反があればその順列は不適格。
   • すべての制約を満たしていれば、スコア \( \sum_{i=0}^{N-1} A[i] \times (\text{順位}_i + 1) \) を計算。
   • 最大スコアを更新。
4. 最終的な最大スコアを出力。

計算量

• 時間計算量: \(O(N! \times M)\)
  • 順列の個数が \(N!\) 個、それぞれに対し最大 \(M\) 個の制約をチェック。
• 空間計算量: \(O(N + M)\)
  • 入力保存用の配列と制約リストのサイズ。

実装のポイント

• 社員番号は入力で1-indexedだが、内部では0-indexedに変換して扱うことで、リストのインデックス操作が楽になる。

• perm.index(i) で社員 \(i\) の順列中での位置（0-indexed）が得られるので、それに1を足して順位とする。

• 制約を満たさない順列は途中で打ち切ることで無駄な計算を減らせる（枝刈り）。

  ソースコード

from itertools import permutations

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    constraints = []
    for i in range(M):
        u = int(data[2+N + 2*i]) - 1  # 0-indexed
        v = int(data[2+N + 2*i + 1]) - 1
        constraints.append((u, v))
    
    max_score = -1
    
    for perm in permutations(range(N)):
        valid = True
        for u, v in constraints:
            if perm.index(u) >= perm.index(v):
                valid = False
                break
        if valid:
            score = sum(A[i] * (perm.index(i) + 1) for i in range(N))
            if score > max_score:
                max_score = score
                
    print(max_score)

if __name__ == "__main__":
    main()

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