概要

高橋君は現在の標高 \(P\) から始めて、他の会員に師事することで自分の到達可能標高を上げていきます。1回の師事にはコスト \(C\) がかかり、最終的に標高 \(T\) 以上にしたいとき、必要な最小コストを求めます。

考察

まず、高橋君が目標の標高 \(T\) に到達できないケースとはどのようなときでしょうか？

• 会員の中に、高橋君の現在の標高 \(P\) より高く、かつ \(T\) 以上の標高に到達できる人がいない場合、どうやっても目標を達成できません。このようなときは -1 を出力します。

次に、目標を達成できる場合を考えましょう。

高橋君は、自分の現在の標高よりも高い会員にしか師事できません。したがって、最初に考えられるのは「自分より高い標高を持つ会員」の中から、できるだけ高いところまで一気に上がるという戦略です。

しかし、このままでは無駄があるかもしれません。例えば、途中で高い会員に師事しても、結局あとでそれより低いけど十分高い会員に師事すればよかった、というケースがあります。

そこで重要な観察があります：

師事する順序は、対象となる会員の標高の昇順に限っても一般性を失いません。
さらに、最終的に得た標高列のうち、本当に必要だったのは「一番最後に師事した人」だけです。

したがって、以下のような貪欲な戦略が有効です：

1. 高橋君より高い標高を持つ会員をすべてリストアップし、降順にソートする。
2. 大きい方から見ていき、「まだ目標 \(T\) に届かないならその人に師事する」という操作を繰り返す。
3. 各ステップで、師事した相手の標高を記録しておき、後で「本当に必要だったか」を判定する。

このようにして、最小回数（＝最小コスト）で目標を達成できます。

また、素朴な全探索などで全ての組み合わせを試すと、最悪の場合 \(O(2^N)\) の計算量となり、間に合いません。今回の制約では最大 \(N = 2 \times 10^5\) なので、線形あるいはそれに近い計算量のアルゴリズムが必要です。

アルゴリズム

1. 高橋君自身の標高 \(P\) がすでに \(T\) 以上であれば、何もせずに 0 を出力。
2. そうでなければ、会員の標高リスト \(S\) から、\(P\) より大きいものだけを取り出し、昇順にソートしておく。
3. これを大きい順に見ながら、以下の処理を行う：
   • 現在の標高がまだ \(T\) 未満なら、その会員に師事（＝現在の標高を更新＋コスト加算）。
   • 師事した会員の標高を優先度付きキュー（最大ヒープ）に入れる。
4. 最後に、実際に目標を達成できたかどうかを確認し、達成できていれば合計コストを出力。できなければ -1 を出力。

このとき、優先度付きキューを使いながら最小コストでの更新を管理することで、無駄な操作を避けることができます。

計算量

• 時間計算量: \(O(N \log N)\)
  （ソートに \(O(N \log N)\)、ヒープ操作に \(O(N \log N)\)）
• 空間計算量: \(O(N)\)
  （候補リストおよびヒープのサイズ）

実装のポイント

• 優先度付きキューをPythonで扱う際は heapq モジュールを使用するが、これは最小ヒープなので、最大値を取り出すために負の値を格納する工夫が必要。

• 入力を高速に読み込むために sys.stdin.read() を使用している。

• 最初に自らが目標を達成しているケースを忘れずにチェックすること。

• 不可能なケース（誰にも師事できない or 目標を超える標高を持つ人がいない）も正確に判定する。

  ソースコード

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    P = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    C = int(data[idx]); idx += 1
    
    if N == 1:
        if P >= T:
            print(0)
        else:
            print(-1)
        return
    
    S = list(map(int, data[idx:idx+N-1]))
    
    # 現在の高橋君の標高
    current = P
    if current >= T:
        print(0)
        return
    
    # 師事できる候補（自分より高い標高の会員）
    candidates = [s for s in S if s > current]
    candidates.sort()  # 昇順ソート
    
    # 最大ヒープを模擬するため、負の値を使って最小ヒープを使う
    heap = []
    cost = 0
    actions = 0
    
    # candidatesを大きい方から見ていく
    for s in reversed(candidates):
        if current >= T:
            break
        if s <= current:
            continue
        # 師事する
        heapq.heappush(heap, -s)  # 最大値を取り出すために負にして格納
        current = s
        cost += C
        actions += 1
        
    # 最後に、heapの中から不要なものを取り除いてコストを最小化
    # heapには選択した候補の標高が入っている（負の値）
    while heap and (-heap[0]) > current:
        heapq.heappop(heap)
        
    # 現在の標高がT以上ならコストを出力
    if current >= T:
        print(cost)
    else:
        # heapの中から、currentを維持するために必要な最小回数を選ぶ
        # つまり、candidatesの中でcurrent以上のものをソートして前から取る
        valid = [s for s in candidates if s >= T]
        if not valid:
            print(-1)
            return
            
        valid.sort()
        # 高橋君がvalid[0]まで到達するには何回師事が必要か？
        # current < valid[0] なので、current未満のものは使えない
        needed = 0
        temp_current = P
        temp_cost = 0
        temp_heap = []
        
        for s in candidates:
            if temp_current >= T:
                break
            if s <= temp_current:
                continue
            heapq.heappush(temp_heap, -s)
            temp_current = s
            temp_cost += C
            needed += 1
            
        if temp_current >= T:
            print(temp_cost)
        else:
            print(-1)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。