概要

高橋君が、レッスン料 \(C\) を支払って自分より高い標高を持つ会員の標高に到達する操作を繰り返し、目標の標高 \(T\) 以上を目指す問題です。最小の合計レッスン料を求めるか、達成不可能なら -1 を出力します。

考察

この問題のポイントは、「目標を達成できるなら、必ず 1 回の操作で達成するのが最善である」という点にあります。

1. 最初から目標を達成している場合 現在の標高 \(P\) がすでに \(T\) 以上であれば、操作を行う必要はありません。このときの費用は \(0\) 円です。

2. 操作が必要な場合（\(P < T\)） 目標を達成するためには、最終的に誰か（会員 \(i\)）に師事して、その標高 \(S_i\) が \(T\) 以上になる必要があります。

   • もし、標高 \(S_i \geq T\) である会員が一人でも存在すれば、高橋君は直接その人に師事することができます。
   • なぜなら、\(P < T\) かつ \(T \leq S_i\) なので、必ず \(P < S_i\)（自分より高い標高）という条件を満たすからです。
   • このときかかる費用は、レッスン 1 回分の \(C\) 円です。

3. 2 回以上の操作は必要か？ レッスン料 \(C\) は正の値であるため、操作回数が少なければ少ないほど総額は安くなります。 もし 2 回以上の操作（例えば会員 A に師事したあと会員 B に師事する）で \(T\) 以上に到達できるなら、最初から会員 B に師事することでも \(T\) 以上に到達可能です（会員 B の標高が \(T\) 以上であれば、初期状態の \(P\) から見ても自分より高い標高であるため）。 したがって、「1 回で到達できるなら 1 回が最小」であり、「1 回で到達できないなら、何回繰り返しても \(T\) 以上にはなれない」ということになります。

4. 達成不可能な場合 すべての会員の標高 \(S_i\) が \(T\) 未満であり、かつ初期標高 \(P\) も \(T\) 未満である場合、どのように操作を繰り返しても標高が \(T\) 以上になることはありません。この場合は -1 を出力します。

アルゴリズム

1. まず、\(P \geq T\) かどうかを確認します。そうであれば 0 を出力して終了します。
2. 次に、会員 \(2\) から \(N\) の中に、標高が \(T\) 以上の人がいるか探します。
3. 一人でもいれば、費用は \(C\) 円なので C を出力します。
4. 一人もいなければ、目標達成は不可能なので -1 を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 会員のリストを 1 回走査して、標高 \(T\) 以上の人がいるか確認するため、会員数 \(N\) に比例した時間がかかります。
• 空間計算量: \(O(N)\)
  • 入力された会員の標高を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 早期リターン: \(P \geq T\) のケースを最初に処理することで、無駄な計算を省けます。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと効率的です。

• ループの最適化: 標高 \(T\) 以上の会員が一人見つかった時点で、残りの会員を確認せずに探索を終了（break）して構いません。

  ソースコード

import sys

def solve():
    # Read all input data at once for efficiency
    # input_data will contain [N, P, T, C, S_2, S_3, ..., S_N]
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Takahashi's initial state and goals
    # N: total number of members (Takahashi is member 1)
    # P: Takahashi's current reachable altitude
    # T: target altitude Takahashi wants to reach
    # C: cost for each training session
    n = int(input_data[0])
    p = int(input_data[1])
    t = int(input_data[2])
    c = int(input_data[3])
    
    # If Takahashi's current altitude is already at or above the target, cost is 0.
    if p >= t:
        print(0)
        return
    
    # If Takahashi needs to increase his altitude (P < T):
    # To reach the target T, he must train with at least one member.
    # Each training session with a member i (where S_i > current altitude)
    # sets Takahashi's altitude to exactly S_i and costs C.
    
    # To minimize total cost, Takahashi should reach the target in the fewest steps.
    # Since each step costs C, the minimum possible non-zero cost is C.
    # This is achievable if there is any member i such that S_i >= T.
    # Since we know P < T, any member with S_i >= T will also satisfy S_i > P,
    # meaning Takahashi can train with them in his very first step.
    
    # If no member has an altitude S_i >= T, Takahashi's altitude can never reach T,
    # because his altitude only changes to an existing member's altitude S_i,
    # and we established all S_i < T and his starting P < T.
    
    # Altitudes S_2, S_3, ..., S_N are stored in input_data starting from index 4.
    found_capable_mentor = False
    for i in range(4, len(input_data)):
        if int(input_data[i]) >= t:
            found_capable_mentor = True
            break
            
    if found_capable_mentor:
        print(c)
    else:
        # If no mentor exists who can help him reach or exceed altitude T
        print(-1)

if __name__ == '__main__':
    solve()

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