概要

山小屋 \(1\) から出発し、一方通行の登山道を辿りながら標高が狭義単調増加になるように山小屋を訪れるとき、最大で何個の山小屋を訪れることができるかを求める問題です。これは DAG（有向非巡回グラフ）上の最長パス問題 に帰着できます。

考察

重要な気づき：グラフは DAG になる

登山道 \(U_j \to V_j\) のうち、実際に「よい縦走」で使えるのは \(P_{U_j} < P_{V_j}\)（出発地より到着地の標高が高い）を満たす辺だけです。使えない辺（\(P_{U_j} \geq P_{V_j}\)）はあらかじめ取り除いてしまって構いません。

残った辺はすべて「標高が低い方から高い方へ」向かっています。すべての山小屋の標高は互いに異なるため、この辺だけで構成されるグラフには 閉路（サイクル）が存在しません。なぜなら、サイクルを辿ると標高が増加し続けて元に戻ることは不可能だからです。

したがって、このグラフは DAG（Directed Acyclic Graph） です。

素朴なアプローチの問題

全探索（DFS で全パスを列挙）すると、パスの数が指数的に増える可能性があり、\(N, M\) が最大 \(2 \times 10^5\) の制約では TLE になります。

解決策

DAG 上の最長パスは トポロジカルソート + 動的計画法（DP） で効率的に求められます。

アルゴリズム

1. グラフ構築: 各辺 \((U_j, V_j)\) について \(P_{U_j} < P_{V_j}\) を満たすもののみ隣接リストに追加します。これにより DAG が得られます。

2. トポロジカルソート: Kahn のアルゴリズム（入次数 0 の頂点から順に取り出す BFS）でトポロジカル順序を求めます。

3. DP で最長パスを計算:

   • \(dp[v]\) を「山小屋 \(1\) から山小屋 \(v\) まで到達できるパス上の山小屋の最大数」と定義します。
   • 初期値: \(dp[1] = 1\)（出発地点）、それ以外は \(dp[v] = 0\)（未到達）。
   • トポロジカル順序に従い、各頂点 \(u\) について、\(dp[u] > 0\)（山小屋 \(1\) から到達可能）ならば、隣接頂点 \(v\) に対して \(dp[v] = \max(dp[v],\ dp[u] + 1)\) と更新します。

4. 答え: \(\max(dp[v])\)（全頂点の中の最大値）を出力します。

具体例

山小屋が 3 つ、標高が \(P = [-, 10, 30, 20]\)（1-indexed）、辺が \(1 \to 2\), \(1 \to 3\), \(3 \to 2\) の場合： - 有効な辺（標高増加）: \(1 \to 2\)（\(10 < 30\)）、\(1 \to 3\)（\(10 < 20\)）、\(3 \to 2\)（\(20 < 30\)） - トポロジカル順: \(1, 3, 2\) - DP: \(dp[1]=1 \to dp[3]=2 \to dp[2]=3\) - 答え: \(3\)（パス: \(1 \to 3 \to 2\)）

計算量

• 時間計算量: \(O(N + M)\) — グラフ構築、トポロジカルソート、DP いずれも頂点数と辺数に線形
• 空間計算量: \(O(N + M)\) — 隣接リスト、入次数配列、DP 配列の格納

実装のポイント

• 辺のフィルタリング: グラフ構築時に \(P[u] < P[v]\) を満たさない辺を除外することで、DAG が保証されます。これを忘れると閉路が生じてトポロジカルソートが正しく動作しません。

• 到達不可能な頂点のスキップ: DP の遷移時に \(dp[u] = 0\) の頂点はスキップします。山小屋 \(1\) から到達できない頂点からの更新を防ぐためです。

• 高速入出力: Python では sys.stdin.buffer.read() でまとめて読み込むことで、大量入力でも TLE を回避しやすくなります。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    P = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = int(input_data[idx]); idx += 1
    
    # We need to find the longest path starting from node 1, 
    # following directed edges, with strictly increasing P values.
    
    # Build adjacency list only for edges where P[u] < P[v] (valid edges)
    adj = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    for j in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        if P[u] < P[v]:
            adj[u].append(v)
            in_degree[v] += 1
    
    # This is a DAG (since edges only go from lower P to higher P, and P values are distinct).
    # We want the longest path from node 1 in this DAG.
    
    # Topological sort using Kahn's algorithm
    topo = []
    queue = deque()
    in_deg = in_degree[:]
    for i in range(1, N + 1):
        if in_deg[i] == 0:
            queue.append(i)
    
    while queue:
        u = queue.popleft()
        topo.append(u)
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)
    
    # DP: longest path from node 1
    # dp[v] = maximum number of nodes in a path from 1 to v
    dp = [0] * (N + 1)
    dp[1] = 1  # start at node 1
    
    for u in topo:
        if dp[u] == 0:
            continue  # not reachable from node 1
        for v in adj[u]:
            if dp[u] + 1 > dp[v]:
                dp[v] = dp[u] + 1
    
    print(max(dp))

if __name__ == '__main__':
    main()

---

この解説は claude4.6opus-thinking によって生成されました。