概要

前提関係を有向グラフで表し、トポロジカルソートを行いながら各タスクの最早完了時刻を求めます。有向閉路がある場合は実行不可能なので -1、そうでなければ最早完了時刻の最大値が答えです。

考察

1. 前提関係を有向グラフで表す

タスクを頂点とし、「タスク \(u\) の完了後にタスク \(v\) を開始できる」という関係を有向辺 \(u \to v\) で表します。

このグラフに有向閉路があると、すべてのタスクを完了させることはできません。例えば \(1 \to 2 \to 1\) という関係があると、

• タスク \(2\) の開始にはタスク \(1\) の完了が必要
• タスク \(1\) の開始にはタスク \(2\) の完了が必要

となり、どちらも開始できません。

より一般に、閉路上の前提条件を足し合わせると、\(S_i \ge S_i + \text{閉路上の所要時間の合計}\) となります。所要時間はすべて正なので、これは矛盾します。

一方、有向閉路がなければ、前提となるタスクから順に処理できます。このような順序を求める手法がトポロジカルソートです。

2. 前提タスクがすべて終わったら、すぐ開始してよい

この問題では、同時に任意の個数のタスクを進められます。そのため、実行可能なタスクをわざと遅らせる必要はありません。

タスク \(v\) の最早完了時刻を \(F_v\) とすると、

• 前提タスクがない場合：時刻 \(0\) に開始できるので \(F_v = A_v\)
• 前提タスクがある場合：それらがすべて完了した直後に開始できるので \(F_v = A_v + \max_{u \to v} F_u\)

となります。

例えば、所要時間が \(A_1 = 3,\ A_2 = 5,\ A_3 = 2\) で、前提関係が \(1 \to 3,\ 2 \to 3\) の場合を考えます。

タスク \(1,2\) は時刻 \(0\) に並行して開始でき、それぞれ時刻 \(3,5\) に完了します。タスク \(3\) は時刻 \(5\) に開始し、時刻 \(7\) に完了するため、答えは \(7\) です。

前提タスクの所要時間を足すのではなく、完了時刻の最大値を使うことが重要です。

3. トポロジカル順で計算すれば、一度の処理で求められる

すべてのタスクを順番に実行すると、並行実行できることを活用できず、最適解にならない場合があります。また、時刻を \(1\) ずつ進めるシミュレーションでは、完了時刻が非常に大きくなるため間に合いません。

そこで、時刻そのものではなく、前提関係の順序に注目します。

トポロジカル順にタスクを処理すれば、タスク \(v\) を処理するときには、その前提タスクの最早完了時刻がすべて確定しています。したがって、上の式を使って効率よく計算できます。

アルゴリズム

入次数を使うトポロジカルソート（Kahn 法）と動的計画法を組み合わせます。入次数とは、その頂点に入ってくる辺の本数です。

1. 各前提関係 \(u \to v\) を隣接リストに追加し、\(v\) の入次数を \(1\) 増やします。
2. 各タスクの最早完了時刻の候補を \(F_i = A_i\) で初期化します。
3. 入次数が \(0\) のタスクをすべてキューに入れます。
4. キューからタスク \(u\) を順に取り出し、次を行います。
   • 答えの候補を \(F_u\) で更新します。
   • 各辺 \(u \to v\) について、\(F_v \gets \max(F_v,\ F_u + A_v)\) と更新します。
   • \(v\) の入次数を \(1\) 減らします。
   • 入次数が \(0\) になったら、\(v\) をキューに追加します。
5. 全 \(N\) 個のタスクを処理できた場合は、\(\max_i F_i\) を出力します。処理できなかった場合は、有向閉路が存在するので -1 を出力します。

なぜ最小値が求まるのか

タスク \(v\) は、すべての前提タスクが完了するまで開始できません。したがって、どのようなスケジュールでも、その完了時刻は \(A_v + \max_{u \to v} F_u\) より早くできません。

一方、並行実行数に制限がないため、すべての前提タスクが完了した時刻に \(v\) を開始すれば、この完了時刻を実現できます。

これをトポロジカル順に適用することで、すべてのタスクについて最早完了時刻が求まります。よって、その最大値がプロジェクト全体の最短完了時刻です。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N + M)\)

各タスクは一度だけキューに追加され、各前提関係も一度だけ処理されます。隣接リストに \(O(N + M)\)、入次数や完了時刻などの配列に \(O(N)\) の空間を使います。

実装のポイント

• 完了時刻は最大値で更新する
  前提タスクが複数ある場合は、すべての完了を待つ必要があります。コードの candidate = current + duration[v] を使い、finish[v] を最大値で更新します。

• 入次数が \(0\) になった時点で完了時刻が確定する
  入次数は「まだ処理していない前提タスクの数」を表します。これが \(0\) になったとき、すべての前提タスクからの更新が済んでいます。

• 提示コードではリストをキューとして使っている
  for u in queue: で走査しながら queue.append(v) で追加すると、追加された要素も順に処理されます。先頭要素を削除しないため、pop(0) による計算量の悪化を避けられます。

• 閉路判定には len(queue) == n を使う
  各タスクは一度だけ追加され、追加されたタスクはすべて処理されます。そのため、最後のリストの長さが \(N\) 未満なら、処理できなかったタスクがあり、有向閉路が存在します。

• 大きな整数に注意する
  完了時刻は最大で \(\sum_i A_i \le 2 \times 10^{14}\) になり得ます。Python の整数では問題ありませんが、他言語では 64 ビット整数型が必要です。

  ソースコード

import sys


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    duration = list(map(int, input().split()))

    graph = [[] for _ in range(n)]
    indegree = [0] * n

    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append(v)
        indegree[v] += 1

    queue = [i for i in range(n) if indegree[i] == 0]
    finish = duration[:]
    answer = 0

    for u in queue:
        current = finish[u]
        if current > answer:
            answer = current

        for v in graph[u]:
            candidate = current + duration[v]
            if candidate > finish[v]:
                finish[v] = candidate
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    print(answer if len(queue) == n else -1)


if __name__ == "__main__":
    main()

---

この解説は gpt-6-astra-medium によって生成されました。