概要

山小屋 \(1\) から出発し、標高が狭義単調増加になるように登山道を辿るとき、訪れることができる山小屋の最大数を求める問題です。

考察

この問題は、グラフ上の「最長パス（最長経路）問題」の一種です。一般に、有向グラフの最長パスを求める問題は非常に計算時間がかかる（NP困難）ことが知られています。そのため、すべての経路を素朴に探索するようなアプローチ（単純な深さ優先探索など）では、計算時間がかかりすぎてTLE（実行時間超過）になってしまいます。

しかし、今回の問題には「連続して訪れる山小屋の標高が狭義単調増加（\(P_{v_i} < P_{v_{i+1}}\)）になっている」という非常に重要な条件があります。

この条件により、標高が下がる方向や同じ標高のまま移動することはできません。つまり、同じ山小屋に二度戻ってくるような「閉路（サイクル）」が絶対に存在しないことになります。このようなサイクルを持たない有向グラフを DAG（有向非巡回グラフ） と呼びます。

グラフがDAGであれば、「動的計画法（DP）」を用いて効率的に最長パスを計算することができます。具体的には、標高が低い山小屋から順番に「そこまで到達するのに最大でいくつの山小屋を経由できたか」を確定させていくことで、正しい答えを導くことができます。

アルゴリズム

1. グラフの構築: 与えられた辺 \(U \to V\) のうち、条件である \(P_U < P_V\) を満たす辺のみを採用して隣接リスト adj を作成します。

2. 頂点のソート: 各山小屋を標高 \(P_i\) の低い順に処理するため、頂点番号 \(1, 2, \dots, N\) を標高の昇順に並び替えたリスト order を作成します。

3. 動的計画法（DP）の準備: 配列 dp[i] を「山小屋 \(1\) から出発して山小屋 \(i\) に到達するときの、訪れる山小屋の最大数」と定義します。 初期値として、未到達であることを表す -1 で埋め、出発点である dp[1] = 1 とします。

4. DPの更新（配るDP）: 標高の低い山小屋 \(u\) （order の要素）から順番に見ていきます。 もし dp[u] が -1 でなければ（山小屋 \(1\) から到達可能であれば）、\(u\) から移動できる隣接する山小屋 \(v\) に対して、以下のように値を更新します。 $\(dp[v] = \max(dp[v], dp[u] + 1)\)$

5. 答えの計算: 到達可能なすべての山小屋における dp[u] の最大値が、求める答えとなります。

計算量

• 時間計算量: \(O(N \log N + M)\)
  • 頂点を標高順にソートするのに \(O(N \log N)\) の時間がかかります。
  • DPの更新では、各頂点と各辺を最大1回ずつしか調べないため \(O(N + M)\) の時間がかかります。
  • 全体として \(O(N \log N + M)\) となり、制約下で十分に高速に動作します。
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストやDP配列などを保持するために使用します。

実装のポイント

• 辺のフィルタリング: 入力を受け取る段階で \(P_U \geq P_V\) となる辺を無視することで、グラフの辺の数を減らし、無駄な処理を省くことができます。

• 到達判定: dp[u] が -1 （未到達）の場合は、そこから先の遷移を行わないように if dp[u] != -1: で弾くことが重要です。

• Python特有の注意: グラフの探索において再帰関数を用いた「メモ化再帰」で実装することも可能ですが、Pythonでは再帰の深さ制限（Recursion Error）に引っかかるリスクがあります。今回のように「ソートしてループで配るDP」を実装することで、再帰上限を気にせずに安全かつ高速に解くことができます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    P = [0] * (N + 1)
    for i in range(N):
        P[i+1] = int(data[2+i])
    
    adj = [[] for _ in range(N + 1)]
    idx = 2 + N
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx+1])
        if P[u] < P[v]:
            adj[u].append(v)
        idx += 2
        
    order = sorted(range(1, N + 1), key=lambda x: P[x])
    
    dp = [-1] * (N + 1)
    dp[1] = 1
    
    ans = 1
    for u in order:
        if dp[u] != -1:
            if dp[u] > ans:
                ans = dp[u]
            nxt_dist = dp[u] + 1
            for v in adj[u]:
                if dp[v] < nxt_dist:
                    dp[v] = nxt_dist
                    
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。