概要

標高が必ず上がるように一方通行の登山道を辿るとき、山小屋 \(1\) から出発して訪れられる山小屋数の最大値（最長経路長）を求めます。

考察

「よい縦走」では、連続する山小屋の標高が \(P_{v_i} < P_{v_{i+1}}\) を満たす必要があります。つまり、実際に使える登山道は 「低い標高 → 高い標高」へ向かう辺だけ です。

ここで重要な観察は次の通りです。

• 標高 \(P_i\) はすべて異なるので、使える辺（\(P_u < P_v\)）だけを残すと、標高が必ず増える方向にしか進めません。
• したがって、このグラフにはサイクルが存在しません（標高が増え続けるのに同じ頂点へ戻れない）。つまり DAG（有向非巡回グラフ） になります。
• DAG 上の「山小屋 1 から始まる最長経路」を求めればよい、という問題に帰着できます。

素朴に「全ての経路を探索する」ような DFS をすると、経路数が指数的に増えうるため \(N, M \le 2 \times 10^5\) では到底間に合いません（TLE）。
そこで、DAG の最長経路は トポロジカル順（ここでは標高の昇順）に DP をすれば線形に計算できます。

アルゴリズム

1. 入力された辺 \((U_j, V_j)\) について、条件 \(P_{U_j} < P_{V_j}\) を満たすものだけを採用し、隣接リスト adj を作る
   
   • 条件を満たさない辺は「よい縦走」では絶対に使えないため捨ててよい
2. 山小屋を標高の昇順に並べた順序 order を作る（これは DAG のトポロジカル順になっています）
3. DP を定義する
   
   • dp[v] = 山小屋 \(1\) から出発して山小屋 \(v\) で終わる「よい縦走」の最大訪問数（到達不可能なら 0）
   • 初期値：dp[0] = 1（山小屋 1 のみで終了する縦走がある）、その他は 0
4. order の順に各頂点 \(u\) を処理し、辺 \(u \to v\) で遷移する
   
   • もし dp[u] = L なら、dp[v] を max(dp[v], L + 1) で更新
5. DP の最大値が答え

（イメージ例）
標高が小さい順に処理していくので、\(u\) を処理する時点で「\(u\) に到達する最適値」は確定しており、その値を使ってより高い標高の頂点へ更新を伝播できます。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  
  • 標高でソートするのに \(O(N\log N)\)、DP の遷移が辺ごとに高々 1 回で \(O(M)\)
• 空間計算量: \(O(N+M)\)
  
  • 隣接リストと DP 配列の分

実装のポイント

• 使える辺だけ残す：入力辺すべてを持つ必要はなく、if P[u] < P[v]: adj[u].append(v) のようにフィルタします（DAG 化でき、無駄な遷移も減ります）。

• 到達不能の管理：dp[u] == 0 の頂点は山小屋 1 から到達できないのでスキップすると効率的です。

• 初期値に注意：問題文より \(k=1\)（山小屋 1 のみ）も許されるため、dp[0]=1、答えの初期値も 1 になります。

• 入力が大きいので sys.stdin.buffer.read() で高速に読み込むのが安全です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    P = [int(next(it)) for _ in range(N)]

    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        if P[u] < P[v]:
            adj[u].append(v)

    order = sorted(range(N), key=lambda i: P[i])

    dp = [0] * N
    dp[0] = 1
    ans = 1

    for u in order:
        du = dp[u]
        if du == 0:
            continue
        ndu = du + 1
        for v in adj[u]:
            if dp[v] < ndu:
                dp[v] = ndu
                if ndu > ans:
                    ans = ndu

    print(ans)

if __name__ == "__main__":
    main()

---

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