概要

制約（先に発表しなければならない関係）を満たす発表順（トポロジカル順序）の中で、\(\sum_{i=1}^{N} A_i P_i\) を最大化する問題です。\(N \le 8\) なので、集合をビットで持つ DP（bit DP）で全探索を高速に行います。

考察

• 発表順 \((P_1,\dots,P_N)\) は「社員を 1 人ずつ並べていく」問題です。ただし、辺 \(U \to V\) があるなら \(U\) を \(V\) より前に置く必要があります（DAG のトポロジカル順序）。
• 目的関数は \(\sum A_i \times P_i\) で、ある社員を「何番目に置くか」によって得点が決まります。
  つまり「今までに誰を置いたか（集合）」が分かれば、次に置く社員を選んだときの増分（\(A_v \times \text{次の位置}\)）が決まります。
• 素朴には全ての順列を試すと \(N!\) 通りですが、制約チェックも含めると実装がやや煩雑です。今回は \(N \le 8\) なので \(N!\) でも通りそうに見えますが、競技プログラミングでは「制約つきの順序最適化」は bit DP に落とすのが定石で、拡張もしやすく安全です。
• そこで、「すでに発表を終えた社員の集合」を状態にして DP をします。次に置けるのは「その社員の前提条件（先に発表すべき社員）が全て集合に入っている」社員だけです。

アルゴリズム

1. 前提条件をビット集合で持つ

社員を \(0\) 〜 \(N-1\) とし、制約 \(u \to v\)（\(u\) が先、\(v\) が後）を読み取って、 - pred[v]：社員 \(v\) の「先に発表していないといけない社員集合」 をビットで持ちます。

例：\(N=4\) で「1 が 3 より先」「2 が 3 より先」なら、（0-indexで）pred[2] は {0,1} のビットが立ちます。

2. bit DP

• 状態 mask：すでに発表を終えた社員集合（ビットが 1 の社員が済み）
• dp[mask]：その状態までで達成できる総合スコアの最大値

初期値： - dp[0] = 0 - それ以外は到達不能として十分小さい値（負の無限大）にする

遷移： - 今 mask にいるとき、次の発表順（位置）は
\(\text{pos} = (\text{mask に含まれる人数}) + 1\)
つまりコードでは pos = mask.bit_count() + 1 - まだ発表していない社員 \(v\) について、次に置ける条件は
「\(v\) の前提社員が全て mask 内にいる」
ビット演算で書くと
pred[v] & ~mask == 0（未達成の前提が無い） - 置けるなら - nmask = mask | (1<<v) - dp[nmask] = max(dp[nmask], dp[mask] + A[v] * pos)

答えは dp[(1<<N)-1]（全員発表済みの状態）です。

計算量

• 時間計算量: \(O(N \cdot 2^N)\)
  （全状態 \(2^N\) に対し、次に置く社員を最大 \(N\) 人試す）
• 空間計算量: \(O(2^N)\)
  （DP 配列）

実装のポイント

• 前提条件チェックは pred[v] & ~mask が 0 かどうかで一発判定できます。~mask はビット反転なので、必要なら「未発表集合」を表していると考えると分かりやすいです。

• dp の初期値は到達不能を表すために十分小さい値（例：-10**30）にしておき、更新時に max を取ります。

• 次の発表順（位置）は「今までに置いた人数 + 1」なので、mask.bit_count() を使うと簡潔です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    pred = [0] * N
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        pred[v] |= 1 << u

    INF_NEG = -10**30
    dp = [INF_NEG] * (1 << N)
    dp[0] = 0

    for mask in range(1 << N):
        if dp[mask] == INF_NEG:
            continue
        pos = mask.bit_count() + 1
        for v in range(N):
            if (mask >> v) & 1:
                continue
            if pred[v] & ~mask:
                continue
            nmask = mask | (1 << v)
            val = dp[mask] + A[v] * pos
            if val > dp[nmask]:
                dp[nmask] = val

    print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。