概要

\(N\) 人の社員に発表順（\(1\) から \(N\) の順列）を割り当て、「社員 \(U_k\) は社員 \(V_k\) より先に発表する」という制約をすべて満たしつつ、\(\sum A_i \times P_i\) を最大化する問題です。

考察

問題の構造を理解する

各社員 \(i\) に発表順 \(P_i\) を割り当てたとき、プレゼン力 \(A_i\) が大きい社員ほど大きな \(P_i\)（遅い発表順）を割り当てると、積 \(A_i \times P_i\) が大きくなり、総合スコアが増えます。

例えば \(N = 3\)、\(A = (1, 3, 2)\) で制約がない場合、\(A_i\) が最大の社員 \(2\) に \(P_2 = 3\)（最後に発表）を割り当てるのが直感的に良さそうです。実際、\(A\) が小さい順に早く発表させるのが最適です。

制約条件の影響

しかし、「社員 \(U_k\) は社員 \(V_k\) より先に発表」という順序制約があるため、単純に \(A_i\) の大きい順に遅く発表させるだけでは制約を破る可能性があります。

\(N \leq 8\) という制約に注目

\(N\) が最大 \(8\) なので、発表順の順列は最大 \(8! = 40320\) 通りしかありません。すべての順列を列挙し、制約を満たすものの中で最大スコアを求める全探索が十分間に合います。

アルゴリズム

1. \((1, 2, \ldots, N)\) の全順列を列挙する。各順列 \(\text{perm}\) は「社員 \(i\)（0-indexed）の発表順が \(\text{perm}[i]\)」を意味する。
2. 各順列について、すべての制約条件 \((U_k, V_k)\) に対して \(\text{perm}[U_k] < \text{perm}[V_k]\) が成り立つかチェックする。
3. 制約を満たす順列について、総合スコア \(\sum_{i=0}^{N-1} A[i] \times \text{perm}[i]\) を計算する。
4. 制約を満たす順列の中での最大スコアを出力する。

具体例

\(N = 3\)、\(A = (1, 3, 2)\)、制約「社員1は社員2より先」（\(P_1 < P_2\)）の場合：

順列 \((P_1, P_2, P_3)\)	\(P_1 < P_2\)?	スコア \(1 \times P_1 + 3 \times P_2 + 2 \times P_3\)
\((1, 2, 3)\)	✓	\(1 + 6 + 6 = 13\)
\((1, 3, 2)\)	✓	\(1 + 9 + 4 = 14\)
\((2, 3, 1)\)	✓	\(2 + 9 + 2 = 13\)
\((3, 2, 1)\)	✗	—
…	…	…

制約を満たすものの中で最大のスコアを選びます。

計算量

• 時間計算量: \(O(N! \times (N + M))\)
  • \(N!\) 通りの順列それぞれに対して、\(M\) 個の制約チェック（\(O(M)\)）とスコア計算（\(O(N)\)）を行う。
  • \(N \leq 8\) なので \(8! \times (8 + 28) = 40320 \times 36 \approx 1.5 \times 10^6\) 程度で十分高速。
• 空間計算量: \(O(N + M)\)

実装のポイント

• 社員番号は問題文で \(1\)-indexed だが、Python の配列は \(0\)-indexed なので、入力時に \(U_k, V_k\) を \(1\) 引いて \(0\)-indexed に変換している。

• itertools.permutations(range(1, N+1)) で発表順 \(1\) 〜 \(N\) の全順列を直接生成できるため、実装がシンプルになる。

• 制約違反が見つかった時点で break して次の順列に移ることで、無駄な計算を省いている。

  ソースコード

import sys
from itertools import permutations

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = []
    for i in range(N):
        A.append(int(input_data[idx])); idx += 1
    constraints = []
    for _ in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        constraints.append((u, v))
    
    best = -1
    for perm in permutations(range(1, N + 1)):
        # perm[i] = P_{i+1}, the presentation order of person i (0-indexed)
        valid = True
        for u, v in constraints:
            if perm[u] >= perm[v]:
                valid = False
                break
        if valid:
            score = sum(A[i] * perm[i] for i in range(N))
            if score > best:
                best = score
    
    print(best)

main()

---

この解説は claude4.6opus-thinking によって生成されました。