概要

\(N\) 曲を順番に演奏するとき、前の曲より難易度が高ければ演奏時間が半分になるという条件のもと、合計演奏時間を求める問題です。

考察

問題の整理

まず、各曲の演奏時間のルールを整理しましょう：

• 1曲目: 必ず \(D_1\) 分かかる
• 2曲目以降: 直前の曲より難易度が狭義単調増加（\(D_{i-1} < D_i\)）なら \(D_i / 2\) 分（切り捨て）、そうでなければ \(D_i\) 分

具体例で理解する

例えば、\(N = 4\)、難易度が \(D = [3, 5, 4, 8]\) の場合：

• 1曲目（難易度3）: 比較対象なし → 3分
• 2曲目（難易度5）: \(3 < 5\) なので半分 → 2分（\(5 / 2 = 2\)）
• 3曲目（難易度4）: \(5 < 4\) は偽なので通常 → 4分
• 4曲目（難易度8）: \(4 < 8\) なので半分 → 4分（\(8 / 2 = 4\)）

合計: \(3 + 2 + 4 + 4 = 13\) 分

なぜシンプルな解法で十分か

この問題は各曲について「直前の曲との比較」だけで演奏時間が決まります。過去の履歴全体を見る必要がなく、1回のループで解けるため、特別なアルゴリズムは不要です。

アルゴリズム

1. 合計時間 total を1曲目の難易度 \(D_0\) で初期化する
2. 2曲目から \(N\) 曲目まで順に見ていく（\(i = 1, 2, \ldots, N-1\)）
   • \(D_{i-1} < D_i\) なら、total に \(D_i / 2\)（切り捨て）を加算
   • そうでなければ、total に \(D_i\) を加算
3. 最終的な total を出力

total = D[0]
for i = 1 to N-1:
    if D[i-1] < D[i]:
        total += D[i] // 2
    else:
        total += D[i]

計算量

• 時間計算量: \(O(N)\)
  • 各曲について1回ずつ処理するため
• 空間計算量: \(O(N)\)
  • 難易度のリストを保存するため

実装のポイント

1. 整数除算の切り捨て: Pythonでは // 演算子を使うことで、小数点以下を切り捨てた整数除算ができます

2. ループの開始位置: 1曲目は特別扱い（必ず \(D_0\) 分）なので、最初に total = D[0] としておき、ループは2曲目（インデックス1）から開始します

3. オーバーフローへの注意: \(D_i\) は最大 \(10^9\)、\(N\) は最大 \(2 \times 10^5\) なので、合計は最大約 \(2 \times 10^{14}\) になりますが、Pythonは多倍長整数を自動で扱うため問題ありません（C++などでは long long が必要）

ソースコード

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

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

print(total)

---

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