概要

タスク間の依存関係（有向グラフ）が与えられ、各タスクの所要時間が決まっているときに、全タスクを完了できる最早の時刻（＝クリティカルパスの長さ）を求める問題です。依存関係に閉路があると実行不可能なので -1 を出力します。

考察

観察 1: これは DAG 上の最長路問題

前提関係「タスク \(V\) を始めるには タスク \(U\) が終わっていること」は、有向辺 \(U \to V\) と見なせます。

各タスク \(i\) について「タスク \(i\) が完了する最早時刻」を \(f_i\) とおきます。すると

• タスク \(i\) に入ってくる辺がない（前提が無い）場合、時刻 \(0\) から始められるので \(f_i = A_i\)
• そうでない場合、すべての前提 \(u \to i\) について \(S_i \ge f_u\) が必要なので、最早の開始時刻は \(\max_{u \to i} f_u\) となり、 $\(f_i = \max_{u \to i} f_u + A_i\)$

答えは \(\max_{1 \le i \le N} f_i\) です。

これは「グラフ上で、入次数 \(0\) の頂点から \(i\) までのパスに含まれる \(A\) の総和の最大値」、つまり DAG の最長路 を求めていることに他なりません。

観察 2: 実行不可能になるのはどんなときか

\(S_{V} \ge S_U + A_U\) かつ \(A_i \ge 1\) なので、辺をたどると開始時刻は必ず真に増加します。よって閉路があると矛盾し、開始時刻の組は存在しません。逆に閉路がない（DAG である）なら、上の \(f_i\) を使って \(S_i = f_i - A_i\) とすればすべての制約を満たせます。

したがって 「実行不可能 ⟺ グラフに閉路が存在する」 です。

素朴なアプローチの問題点

• 「メモ化再帰（DFS）で \(f_i\) を求める」方針自体は正しいですが、Python では \(N = 2 \times 10^5\) の深さの再帰でスタックオーバーフローを起こす危険があり、また閉路検出も別途必要になります。
• 「時刻を \(1\) ずつ進めてシミュレーション」は \(A_i \le 10^9\) より答えが \(10^{14}\) 規模になり得るので全く間に合いません。
• 隣接リストを adj = [[] for _ in range(n+1)] のようにリストのリストで持つと、Python では定数倍が重くなりがちです（本問の制約なら通ることも多いですが、後述の CSR 形式が安全です）。

これらは トポロジカルソート（Kahn のアルゴリズム） を使えば、閉路検出と最長路計算を同時に、非再帰で \(O(N+M)\) で解決できます。

アルゴリズム

Kahn のアルゴリズム（BFS 型トポロジカルソート）で処理します。

1. 各頂点の入次数 indeg[v] を数える。
2. finish[i] を \(A_i\) で初期化する（前提が全くない場合の完了時刻）。
3. indeg[i] == 0 の頂点をすべてキューに入れる。
4. キューから頂点 \(u\) を取り出す。この時点で \(u\) に入る辺はすべて処理済みなので、finish[u] は確定値である。答えを ans = max(ans, finish[u]) で更新する。
5. \(u\) の各出辺 \(u \to v\) について
   • finish[v] = max(finish[v], finish[u] + A[v])
   • indeg[v] -= 1、\(0\) になったらキューに push
6. 処理した頂点数が \(N\) 未満なら閉路があるので -1、そうでなければ ans を出力。

なぜ正しいか: トポロジカル順で処理するため、頂点 \(v\) をキューから取り出すときには、\(v\) に入る全ての辺 \(u \to v\) の \(u\) が既に確定・処理済みです。よって finish[v] には \(\max_{u \to v} f_u + A_v\) が正しく入っています。

具体例

\(N=4\), \(A = (3, 1, 4, 2)\)、辺が \(1\to3, 2\to3, 3\to4\) のとき

• indeg = (0,0,2,1)、初期 finish = (3,1,4,2)
• 頂点 \(1\) を処理: ans=3、finish[3] = max(4, 3+4) = 7、indeg[3]=1
• 頂点 \(2\) を処理: ans=3、finish[3] = max(7, 1+4) = 7、indeg[3]=0 → push
• 頂点 \(3\) を処理: ans=7、finish[4] = max(2, 7+2) = 9、push
• 頂点 \(4\) を処理: ans=9

答えは \(9\)。

計算量

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

実装のポイント

• 入力の高速化: sys.stdin.buffer.read().split() で一括読み込みします。\(N = 2\times10^5\), \(M = 10^5\) 行なので input() の連続呼び出しは避けたいところです。

• 隣接リストを CSR（圧縮隣接リスト）形式で持つ:

  start[i] : 頂点 i の出辺が adj のどこから始まるか
  adj[start[i] : start[i+1]] : 頂点 i の行き先の列
  

  まず各頂点の出次数 cnt を数え、その累積和で start を作り、もう一度辺を走査して adj に詰めます。Python のリストのリストよりオブジェクト数が少なく、定数倍が軽くなります。

• 再帰を使わない: deque を使った BFS 型なので、深さ \(2\times 10^5\) でも安全です（DFS の再帰だと RecursionError のリスクがあります）。

• 閉路判定: processed != n で判定します。閉路に含まれる頂点は入次数が \(0\) にならず、永遠にキューに入らないためです。

• オーバーフローの心配は不要: 最大 \(2\times10^5 \times 10^9 = 2\times10^{14}\) ですが Python の整数は多倍長なので問題ありません（C++ なら long long を使う必要があります）。

• finish の初期値を \(A_i\) にしておくことで、入次数 \(0\) の頂点（時刻 \(0\) 開始）を特別扱いせずに済みます。

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    A = [0]*(n+1)
    for i in range(1, n+1):
        A[i] = int(data[idx]); idx += 1
    indeg = [0]*(n+1)
    us = [0]*m
    vs = [0]*m
    cnt = [0]*(n+2)
    for j in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        us[j] = u
        vs[j] = v
        cnt[u] += 1
        indeg[v] += 1
    start = [0]*(n+2)
    s = 0
    for i in range(1, n+1):
        start[i] = s
        s += cnt[i]
    start[n+1] = s
    pos = start[:]
    adj = [0]*m
    for j in range(m):
        u = us[j]
        adj[pos[u]] = vs[j]
        pos[u] += 1

    finish = [0]*(n+1)
    for i in range(1, n+1):
        finish[i] = A[i]
    q = deque()
    for i in range(1, n+1):
        if indeg[i] == 0:
            q.append(i)
    processed = 0
    ans = 0
    while q:
        u = q.popleft()
        processed += 1
        fu = finish[u]
        if fu > ans:
            ans = fu
        for k in range(start[u], start[u+1]):
            v = adj[k]
            nf = fu + A[v]
            if nf > finish[v]:
                finish[v] = nf
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if processed != n:
        sys.stdout.write("-1\n")
    else:
        sys.stdout.write(str(ans) + "\n")

main()

---

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