概要

\(N\) 人の社員の発表順を、与えられた前後関係の制約を満たすように決める問題です。その際、各社員の「プレゼン力 \(\times\) 発表順」の合計である総合スコアが最大になるような発表順を探し出し、その最大値を出力します。

考察

この問題で最も注目すべき点は、社員の人数 \(N\) の制約が \(1 \leq N \leq 8\) と非常に小さいことです。

\(N\) 人の発表順の決め方（順列）は全部で \(N!\)（\(N\) の階乗）通りあります。最大の \(N=8\) の場合でも、\(8! = 40,320\) 通りしかありません。 それぞれの発表順について、 1. 制約を満たしているかを確認する 2. 満たしているなら総合スコアを計算する

という処理を行っても、計算回数は高々数十万回程度に収まります。これは現代のコンピュータ（およびPython）であれば制限時間内に余裕で処理できる回数です。

もし \(N\) がもっと大きい場合は、動的計画法などを考える必要がありますが、今回は \(N \leq 8\) であるため、「考えられるすべての発表順を試し、条件を満たすものの中で最大のスコアを探す」という全探索（順列全探索） のアプローチで確実に正解することができます。

アルゴリズム

1. Pythonの標準ライブラリである itertools.permutations を使用して、\(0\) から \(N-1\) までの社員番号の並び替え（順列）をすべて生成します。この順列の \(i\) 番目の要素が、「\(i\) 番目に発表する社員」を表します。
2. 生成した順列から、各社員が「何番目に発表するか」を記録した配列 pos を作成します。例えば、社員 \(u\) の発表順は pos[u] で取得できるようにします。
3. 与えられた \(M\) 個の制約 \((U_k, V_k)\) を一つずつ確認します。もし pos[U_k] > pos[V_k] となっている（\(U_k\) が \(V_k\) より後に発表する）場合は、この順列は条件を満たさないためスキップします。
4. すべての制約を満たした場合、総合スコア \(\displaystyle\sum_{i=0}^{N-1} A_i \times (\text{pos}[i] + 1)\) を計算します。（問題文の発表順は \(1\) 始まりのため、pos[i] に \(1\) を足しています）
5. 計算したスコアで最大値を更新していき、すべての順列を試し終わった後の最大値が答えとなります。

計算量

• 時間計算量: \(O(N! \times (N + M))\)
  • \(N!\) 通りのすべての順列に対して、発表順配列の作成に \(O(N)\)、制約の確認に \(O(M)\)、スコア計算に \(O(N)\) の時間がかかります。最大の \(N=8, M=28\) の場合でもループの内部処理は数百万回程度に収まり、十分に高速です。
• 空間計算量: \(O(N + M)\)
  • プレゼン力 \(A\) や発表順 pos の保持に \(O(N)\)、制約条件の保持に \(O(M)\) のメモリを使用します。

実装のポイント

• 0-indexed（0始まり）への変換: 入力で与えられる社員番号や制約は \(1\) から \(N\) で与えられますが、プログラム内部では配列のインデックスに合わせて \(0\) から \(N-1\) で扱うと実装がすっきりします。入力の段階で \(U_k, V_k\) から \(1\) を引いておきましょう。

• スコア計算時の補正: 内部では順番を \(0\) から \(N-1\) で管理していますが、スコア計算の定義では発表順 \(P_i\) は \(1\) から \(N\) です。そのため、スコアを計算する際は pos[i] + 1 を掛けることを忘れないように注意が必要です。

• 順列の扱い: permutations(range(N)) で生成されるのは「順番に並んだ社員の番号」です。制約のチェックやスコア計算を簡単にするために、「社員 \(i\) が何番目か」を逆引きできる配列 pos を都度作成するのがポイントです。

  ソースコード

import sys
from itertools import permutations

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    
    A = [int(x) for x in data[2:2+N]]
    
    constraints = []
    idx = 2 + N
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx+1]) - 1
        constraints.append((u, v))
        idx += 2
        
    ans = -1
    for p in permutations(range(N)):
        pos = [0] * N
        for i, emp in enumerate(p):
            pos[emp] = i
            
        ok = True
        for u, v in constraints:
            if pos[u] > pos[v]:
                ok = False
                break
                
        if ok:
            score = sum(A[i] * (pos[i] + 1) for i in range(N))
            if score > ans:
                ans = score
                
    print(ans)

if __name__ == '__main__':
    main()

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