概要

高橋君が \(N\) 曲のピアノを順番に演奏するとき、難易度が前曲より高い場合に演奏時間が半分になる条件を考慮して、合計演奏時間を求める問題。

考察

この問題では、各曲の演奏時間が「前曲より難易度が高いかどうか」によって変化します。具体的には：

• 最初の曲は無条件に \(D_1\) 分かかる。
• それ以降の曲について、\(D_{i-1} < D_i\) なら時間は \(D_i / 2\)（小数点以下切り捨て）となり、そうでない場合は \(D_i\) 分かかる。

素朴な方法として、毎回直前の難易度と比較しながら時間を足していくシミュレーションを行えばよいことがわかります。これは一度の走査で済むため、非常に効率的です。

もし「連続増加列をまとめて処理する」ような複雑なロジックを使おうとすると、実装が難しくなるだけでなく、余計な計算量がかかってTLEになる可能性もあります。しかし、この問題では単純な逐次処理で十分高速に動作します。

アルゴリズム

1. 最初の曲の難易度 \(D_1\) を total_time に加算する（最初の曲は常に通常時間）。
2. 2曲目以降について、以下のように処理を行う：
   • もし前曲の難易度 \(D_{i-1}\) より現在の曲の難易度 \(D_i\) が大きければ、\(D_i / 2\) を total_time に加算する。
   • そうでなければ、\(D_i\) をそのまま total_time に加算する。
3. 全ての曲を処理したら、total_time を出力する。

例

入力例：

5
10 20 15 30 25

計算過程：

• 曲1：10分 → 合計：10
• 曲2：20 > 10 → 半分 → 10分 → 合計：20
• 曲3：15 < 20 → 通常 → 15分 → 合計：35
• 曲4：30 > 15 → 半分 → 15分 → 合計：50
• 曲5：25 < 30 → 通常 → 25分 → 合計：75

答え：75

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （難易度リストの保持）

実装のポイント

• 最初の曲だけは特別扱いして、必ず通常時間で加算すること。
• 整数除算（//）を使うことで、小数点以下切り捨てを自然に表現できる。
• 入力をリストで受け取るのがシンプルで安全。

ソースコード

N = int(input())
D = list(map(int, input().split()))

total_time = D[0]

for i in range(1, N):
    if D[i-1] < D[i]:
        total_time += D[i] // 2
    else:
        total_time += D[i]

print(total_time)

---

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