概要

前提関係を有向グラフとして表し、閉路検出（実行不可能かの判定）とトポロジカルソートを用いた動的計画法（DAG上の最長経路問題）により、プロジェクト全体の最短完了時刻を求める問題です。

考察

1. グラフへの帰着

タスクを頂点、前提関係 \(U_j \to V_j\) を有向辺とする有向グラフを考えます。 「タスク \(V\) を開始するためには、タスク \(U\) が完了していなければならない」という条件から、タスク \(V\) の開始時刻 \(S_V\) は、自身に先行するすべてのタスク \(U\) について \(S_V \ge S_U + A_U\) を満たす必要があります。

全体の完了時刻を最小化するには、各タスクを「開始可能な最も早い時刻」に開始するのが最適です。したがって、先行タスクがないタスクは時刻 \(0\) に開始し、先行タスクがあるタスク \(V\) の開始時刻は以下のように決まります。 $\(S_V = \max_{U \to V} (S_U + A_U)\)$

2. 閉路の検出（実行不可能性の判定）

もしグラフに有向閉路（サイクル）が存在する場合、「A が終わらないと B が始まらず、B が終わらないと A が始まらない」というデッドロックが発生します。この場合、前提関係をすべて満たす開始時刻の割り当ては存在しないため、-1 を出力します。

3. DAG 上の動的計画法

閉路が存在しない場合、このグラフは DAG（有向非巡回グラフ） となります。 DAG では、前提となるタスクから順に処理を行う（トポロジカル順序に沿って値を更新する）ことで、各タスクの最も早い開始時刻を一意に決定することができます。

アルゴリズム

Kahn のアルゴリズム（入次数を用いた BFS） を利用して、トポロジカルソートと同時に動的計画法（DP）を行います。

1. 初期化:

   • 各頂点の入次数（前提タスクの数）をカウントします。
   • 各頂点 \(i\) の最も早い開始時刻を記録する配列 dp[i] を \(0\) で初期化します。
   • 入次数が \(0\) の頂点（先行タスクがないタスク）をキューに追加します。

2. 探索と更新:

   • キューから頂点 \(u\) を取り出し、訪問した頂点数を \(1\) 増やします。
   • \(u\) から伸びる辺の先にある各頂点 \(v\) について:
     • 開始時刻を更新します: dp[v] = max(dp[v], dp[u] + A[u])
     • \(v\) の入次数を \(1\) 減らします。
     • \(v\) の入次数が \(0\) になった場合、\(v\) の先行タスクがすべて完了したことを意味するため、キューに \(v\) を追加します。

3. 判定と答えの計算:

   • キューが空になった後、訪問した頂点数が \(N\) 未満であれば閉路が存在するため -1 を出力します。
   • 訪問数が \(N\) であれば、全タスクの完了時刻の最大値 \(\max_{1 \le i \le N} (dp[i] + A_i)\) が答えとなります。

計算量

• 時間計算量: \(O(N + M)\)
  • 各頂点および各辺を高々 \(1\) 回ずつ調べるため、線形時間で動作します。\(N \le 2 \times 10^5, M \le 10^5\) の制約下で十分に高速です。
• 空間計算量: \(O(N + M)\)
  • グラフを表現する隣接リスト、入次数配列、DP 配列を保持するために必要なメモリです。

実装のポイント

• オーバーフローへの注意:

  • 各タスクの所要時間 \(A_i\) は最大で \(10^9\) です。タスクが直列に並んでいる場合、完了時刻は最大で \(N \times \max(A_i) \approx 2 \times 10^{14}\) に達し、32bit 整数型（int）の範囲を超えてしまいます。そのため、dp 配列や答えの計算には 64bit 整数型（C++ の long long）を使用する必要があります。

    ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> adj(n);
    vector<int> in_degree(n, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        in_degree[v]++;
    }

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<long long> dp(n, 0);
    int visited_count = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        visited_count++;

        for (int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + a[u]);
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (visited_count < n) {
        cout << -1 << "\n";
        return 0;
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dp[i] + a[i]);
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.8-flash-high によって生成されました。