概要

タスクの前提関係を有向グラフとして捉え、グラフに閉路（サイクル）が存在するかを判定しつつ、トポロジカルソートを用いて各タスクの最早開始時刻を順に求める問題です。

考察

グラフとしてのモデル化

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

全体の完了時刻を最小化するには、各タスクを可能な限り早く開始するのが最適です。したがって、各タスクの開始時刻は以下のように決まります： - 前提関係がないタスク：時刻 \(0\) に開始（\(S_V = 0\)） - 前提関係があるタスク：すべての前提タスクが終了した瞬間に開始（\(S_V = \max_{U \to V} (S_U + A_U)\)）

閉路の検出

もしグラフに閉路（例: タスク \(1 \to 2 \to 3 \to 1\) という依存のループ）が存在する場合、「タスク \(1\) を始めるにはタスク \(1\) 自身が終わっていなければならない」という矛盾が生じ、条件を満たす開始時刻の組は存在しません。この場合は -1 を出力する必要があります。 閉路が存在しないグラフを有向非巡回グラフ（DAG: Directed Acyclic Graph）と呼びます。

最早開始時刻の計算

DAG であれば、頂点を「前提関係の依存順」に並べるトポロジカルソートを行うことで、先行するタスクの完了時刻を確定させた上で次のタスクの最早開始時刻を順次計算していくことができます。

アルゴリズム

入次数（その頂点に入ってくる辺の本数）を管理する Kahn のアルゴリズム（BFS によるトポロジカルソート） を用います。

1. 初期化:
   • 各頂点の入次数を数えます。
   • 各タスクの開始時刻の配列 \(S\) を \(0\) で初期化します。
   • 入次数が \(0\) の頂点（前提タスクがない頂点）をすべてキュー（deque）に入れます。
2. キューを用いた探索:
   • キューから頂点 \(u\) を \(1\) つ取り出します（この時点で \(S_u\) は確定しています）。
   • 処理した頂点数 count を \(1\) 増やします。
   • 頂点 \(u\) の終了時刻 \(S_u + A_u\) を計算し、\(u\) から伸びる各辺 \(u \to v\) について：
     • \(S_v\) を \(\max(S_v, S_u + A_u)\) に更新します。
     • 頂点 \(v\) の入次数を \(1\) 減らします。
     • 頂点 \(v\) の入次数が \(0\) になったら、頂点 \(v\) の前提がすべて処理されたことになるため、キューに追加します。
3. 答えの判定:
   • 処理した頂点数 count が \(N\) 未満の場合、グラフに閉路が存在して途中で処理が止まったことを意味するため、-1 を出力します。
   • count が \(N\) の場合、すべてのタスクについて計算できています。全体の完了時刻はすべてのタスクの終了時刻の最大値 \(\max_{1 \le i \le N} (S_i + A_i)\) となるので、これを出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • グラフの構築に \(O(N + M)\)、各頂点および各辺をキューを用いてちょうど \(1\) 回ずつ走査するため、全体で \(O(N + M)\) となり実行時間制限に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 隣接リスト、入次数配列、開始時刻配列 \(S\) などを保持するために \(O(N + M)\) のメモリを使用します。

実装のポイント

• 大きな値への対応:

  • \(A_i\) は最大 \(10^9\) であり、タスクが直列に \(N\) 個並んだ場合、終了時刻は最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) に達します。Python では自動的に多倍長整数として扱われるためオーバーフローの心配はありませんが、C++ などの言語では 64bit 整数型（long long）を使用する必要があります。

• 再帰深度の回避:

  • DFS を用いたトポロジカルソートでも実装可能ですが、頂点数が \(N \le 2 \times 10^5\) と大きいため、Python では再帰深度の上限（RecursionError）に注意が必要です。BFS（Kahn のアルゴリズム）を用いることで、再帰深度を気にせず安全に実装できます。

    ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    A = [int(x) for x in input_data[2:2+N]]
    
    adj = [[] for _ in range(N)]
    in_degree = [0] * N
    
    idx = 2 + N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        adj[u].append(v)
        in_degree[v] += 1
        idx += 2
        
    queue = deque([i for i in range(N) if in_degree[i] == 0])
    S = [0] * N
    
    count = 0
    while queue:
        u = queue.popleft()
        count += 1
        finish_u = S[u] + A[u]
        for v in adj[u]:
            if finish_u > S[v]:
                S[v] = finish_u
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    if count < N:
        print(-1)
    else:
        ans = 0
        for i in range(N):
            finish_i = S[i] + A[i]
            if finish_i > ans:
                ans = finish_i
        print(ans)

if __name__ == '__main__':
    main()

---

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