概要

高橋君が目標標高 \(T\) 以上に到達するために、何回レッスンを受ける必要があるかを求める問題です。レッスンは「自分より高い標高を持つ人」からのみ受けられるという制約があります。

考察

重要な気づき

1. レッスンの制約: 高橋君は「自分より厳密に高い到達可能標高を持つ会員」からしか学べません
2. レッスン後の標高: レッスンを受けると、師事した会員と同じ標高になります
3. 目標: 最終的に標高 \(T\) 以上になればよい

場合分け

いくつかのケースを考える必要があります：

1. すでに目標達成: \(P \geq T\) なら、レッスン不要（コスト \(0\)）
2. 会員が自分だけ: \(N = 1\) なら、師事できる人がいない（達成不可能）
3. 誰も目標に届かない: 全会員の最大標高が \(T\) 未満なら達成不可能

最適戦略の考察

目標を達成できる場合、どうすれば最小コストで到達できるでしょうか？

例: \(P = 100\), \(T = 500\), 他会員の標高が \([150, 300, 600]\) の場合 - 直接 \(600\) の人に師事 → 1回で達成！（コスト \(C\)）

例: \(P = 100\), \(T = 500\), 他会員の標高が \([150, 300, 400]\) の場合 - 誰も \(500\) 以上に到達できないので、達成不可能

例: \(P = 100\), \(T = 500\), 他会員の標高が \([50, 500]\) の場合 - \(500\) の人は \(P = 100\) より高いので師事可能 → 1回で達成！

貪欲法の正当性

毎回「現在の自分より高い標高を持つ人の中で最大の標高を持つ人」に師事するのが最適です。 - 中途半端な標高の人に師事しても、最終的に必要なレッスン回数が減ることはありません - 最大標高の人に師事すれば、次のステップで選べる選択肢が最も広がります

アルゴリズム

1. \(P \geq T\) なら 0 を出力して終了
2. \(N = 1\) なら -1 を出力して終了
3. 他会員の標高リストを読み込み、最大値が \(T\) 未満なら -1 を出力して終了
4. 貪欲法でシミュレーション：
   • 現在の標高 current を \(P\) で初期化
   • current < T の間、以下を繰り返す：
     • current より大きい標高の中で最大値を探す
     • 見つからなければ -1（実際にはステップ3で弾かれるはず）
     • 見つかれば current を更新し、コストに \(C\) を加算
5. 最終的なコストを出力

計算量

• 時間計算量: \(O(N \times K)\)（\(K\) はレッスン回数、最悪 \(O(N^2)\)）
  • 各レッスンで全会員を走査するため
  • ただし実際には、貪欲に最大を選ぶため \(K\) は高々 \(N-1\) 回
• 空間計算量: \(O(N)\)（会員の標高リストを保持）

実装のポイント

1. 初期状態のチェック: \(P \geq T\) の場合を最初に処理することで、以降のロジックを簡潔に保てます

2. N = 1 の特別処理: 2行目の入力が空になるため、先にチェックが必要です

3. 直接到達できるケース: 標高が \(T\) 以上かつ \(P\) より大きい会員がいれば、1回のレッスンで目標達成できます

4. ループの終了条件: current >= T になった時点でループを抜けます。目標は「\(T\) 以上」なので、ちょうど \(T\) でなくても問題ありません

   ソースコード

def solve():
    line1 = input().split()
    N, P, T, C = int(line1[0]), int(line1[1]), int(line1[2]), int(line1[3])
    
    # If already at or above target
    if P >= T:
        print(0)
        return
    
    # N=1 means only Takahashi exists, no one to learn from
    if N == 1:
        print(-1)
        return
    
    # Read other members' heights
    S = list(map(int, input().split()))
    
    # Find the maximum height among other members that is greater than P
    # We need to find if there's anyone with height >= T
    max_height = max(S)
    
    # If no one can reach T or higher, impossible
    if max_height < T:
        print(-1)
        return
    
    # Otherwise, we can achieve the goal
    # Strategy: We need to reach height >= T
    # Each lesson costs C, and we can only learn from someone with strictly higher altitude
    
    # The optimal strategy is to find someone with height >= T and learn from them
    # But we can only learn from someone with strictly higher altitude than our current
    
    # If there exists someone with height >= T and height > P, we can learn directly (cost C)
    # Otherwise, we need to chain: learn from someone > P, then learn from someone >= T
    
    # Check if there's anyone with height >= T and height > P
    can_reach_directly = any(s >= T and s > P for s in S)
    
    if can_reach_directly:
        print(C)
        return
    
    # Otherwise, we need to check if we can reach someone with height >= T through chaining
    # We need: someone with height > P, and someone with height >= T
    # Since we already checked max_height >= T, we know someone has height >= T
    # But that person might have height <= P
    
    # For chaining to work:
    # 1. Find someone with height h1 where h1 > P
    # 2. After learning from them, find someone with height h2 where h2 > h1 and h2 >= T
    # Or directly find someone with height >= T and > P
    
    # Since the direct case is already handled, we need chaining
    # For chaining: we need heights that form a strictly increasing sequence from P to >= T
    
    # The minimum chain: find heights > P, then from the maximum reachable, find heights > that, etc.
    # 
    # Greedy approach: always jump to the maximum available height > current height
    
    current = P
    cost = 0
    
    while current < T:
        # Find max height strictly greater than current
        next_height = -1
        for s in S:
            if s > current:
                next_height = max(next_height, s)
        
        if next_height == -1:
            # Can't improve anymore
            print(-1)
            return
        
        current = next_height
        cost += C
    
    print(cost)

solve()

---

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