概要

台風によって倒れてしまった果樹（高さが \(T\) 以下のもの）を特定し、それらをすべて植え直すために必要なコストの合計を求める問題です。

考察

この問題でやるべきことは非常にシンプルです。各果樹 \(i\) について以下の手順を繰り返します。

1. 果樹 \(i\) の高さ \(H_i\) が、基準値 \(T\) 以下であるかを確認する。
2. もし \(H_i \leq T\) であれば、その果樹は倒れているので、復旧コスト \(C_i\) を合計値に加算する。
3. すべての果樹について確認が終わったら、合計値を出力する。

注意点： - 制約と計算量: 果樹の本数 \(N\) は最大で \(2 \times 10^5\) です。1本ずつ順番に確認していく方法（線形探索）をとれば、計算回数は \(N\) 回に比例するため、制限時間内に十分に間に合います。 - 数値の大きさ: 合計コストは最大で \(2 \times 10^{14}\) に達することが保証されています。Pythonでは大きな整数も自動的に扱えますが、他の言語（C++など）では 64bit 整数型（long long など）を使用する必要があります。

アルゴリズム

1. 総コストを保持する変数 total_cost を \(0\) で初期化します。
2. 果樹の番号 \(i = 1, 2, \ldots, N\) について、順番に以下の処理を行います。
   • もし \(H_i \leq T\) ならば、total_cost に \(C_i\) を足す。
   • そうでなければ（\(H_i > T\) の場合）、何もしない。
3. 最終的な total_cost の値を出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 本の果樹を 1 回ずつ走査するため、果樹の数に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) すべての果樹の高さ \(H_i\) とコスト \(C_i\) をリストに格納して保持するため、入力サイズに比例したメモリを使用します。

実装のポイント

• 効率的な入力: \(N\) が \(2 \times 10^5\) と比較的大きいため、Pythonで input() を何度も呼び出すと実行時間が長くなることがあります。sys.stdin.read().split() を使って全ての入力を一度に読み込み、リストとして処理することで高速化が期待できます。

• 型変換: 入力データは文字列として読み込まれるため、比較演算（<=）や加算を行う前に必ず int() を使って整数型に変換する必要があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # N: 果樹の本数, T: 台風の影響を受ける高さの閾値
    N = int(input_data[0])
    T = int(input_data[1])
    
    # H: 各果樹の高さのリスト (インデックス 2 から N+1 まで)
    # C: 各果樹の復旧コストのリスト (インデックス N+2 から 2*N+1 まで)
    H = input_data[2:N+2]
    C = input_data[N+2:2*N+2]
    
    total_cost = 0
    
    # 各果樹について、高さが T 以下であればコストを加算します
    for i in range(N):
        # 比較のために整数型に変換します
        if int(H[i]) <= T:
            total_cost += int(C[i])
            
    # 合計コストを出力します
    print(total_cost)

if __name__ == "__main__":
    solve()

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