概要

高さが基準値 \(T\) 以下の果樹をすべて見つけ、それらを植え直すコストの合計を求める問題です。

考察

この問題で重要な気づきは以下の通りです：

問題の本質

• 各果樹について「倒れたかどうか」を判定する条件は \(H_i \leq T\) という単純な不等式
• 倒れた果樹のコスト \(C_i\) をすべて足し合わせれば答えが得られる

素朴なアプローチで十分か？

この問題は、各果樹を1回ずつ確認すれば解けます。\(N\) 本の果樹それぞれについて条件判定を行い、該当するものだけコストを加算するという素朴な方法で、計算量は \(O(N)\) となり十分高速です。

具体例で確認

例えば、\(N = 4\)、\(T = 5\) で以下の場合を考えます： - 高さ: \(H = [3, 7, 5, 10]\) - コスト: \(C = [100, 200, 150, 300]\)

各果樹を順番に見ていくと： - 果樹1: \(H_1 = 3 \leq 5\) → 倒れた → コスト 100 を加算 - 果樹2: \(H_2 = 7 > 5\) → 倒れていない - 果樹3: \(H_3 = 5 \leq 5\) → 倒れた → コスト 150 を加算 - 果樹4: \(H_4 = 10 > 5\) → 倒れていない

総コスト = \(100 + 150 = 250\)

アルゴリズム

1. 総コストを管理する変数 total_cost を \(0\) で初期化
2. \(i = 0, 1, \ldots, N-1\) について以下を繰り返す：
   • \(H_i \leq T\) ならば、total_cost に \(C_i\) を加算
3. 最終的な total_cost を出力

このアルゴリズムは、配列を1回走査するだけのシンプルな線形探索です。

計算量

• 時間計算量: \(O(N)\)
  • 各果樹を1回ずつ確認するため
• 空間計算量: \(O(N)\)
  • 入力の配列 \(H\), \(C\) を保持するため

実装のポイント

1. オーバーフローに注意: 制約より \(C_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、総コストは最大で約 \(2 \times 10^{14}\) になり得ます。Python では整数のオーバーフローを気にする必要はありませんが、C++ などの言語では long long 型を使用する必要があります。

2. 境界条件の確認: 条件は \(H_i \leq T\)（\(<\) ではなく \(\leq\)）であることに注意してください。高さがちょうど \(T\) の果樹も倒れます。

3. 倒れた果樹がない場合: すべての果樹の高さが \(T\) より大きい場合、total_cost は初期値の \(0\) のまま出力されます。これは問題の要求通りです。

   ソースコード

N, T = map(int, input().split())
H = list(map(int, input().split()))
C = list(map(int, input().split()))

total_cost = 0
for i in range(N):
    if H[i] <= T:
        total_cost += C[i]

print(total_cost)

---

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