概要

曲を順番に演奏するとき、直前の曲より難易度が高い曲だけ演奏時間が半分（切り捨て）になるので、その規則に従って合計時間を求める問題です。

考察

重要なのは「各曲の演奏時間が、直前の曲との大小関係 \(D_{i-1} < D_i\) のみで決まる」点です。
つまり、\(i\) 番目の曲の時間は

• \(i=1\) のとき：必ず \(D_1\)
• \(i\ge 2\) のとき：
  • もし \(D_{i-1} < D_i\) なら \(\left\lfloor \dfrac{D_i}{2} \right\rfloor\)
  • そうでなければ \(D_i\)

となります。

この条件は「連続して増加している区間全体」を意識しなくても、結局は各 \(i\) で直前との比較だけ見れば十分です（増加が続いているかどうかは、毎回 \(D_{i-1} < D_i\) を満たすかで自動的に反映されるため）。

具体例

\(D=[3,5,4,6]\) のとき

• 1曲目: \(3\)
• 2曲目: \(3<5\) なので \(\lfloor 5/2 \rfloor =2\)
• 3曲目: \(5<4\) ではないので \(4\)
• 4曲目: \(4<6\) なので \(\lfloor 6/2 \rfloor =3\)

合計は \(3+2+4+3=12\) 分です。

素朴に「増加区間を探してまとめて処理する」などもできますが、結局やることは隣接比較の繰り返しなので、1回の走査で十分です。\(N\le 2\times 10^5\) なので \(O(N)\) で確実に間に合います。

アルゴリズム

1. 合計時間 total を \(D_1\) で初期化する（1曲目は必ずそのまま）。
2. \(i=2\) から \(N\) まで順に見ていく：
   • もし \(D_{i-1} < D_i\) なら total += D_i // 2
   • それ以外なら total += D_i
3. total を出力する。

計算量

• 時間計算量: \(O(N)\)（1回のループで隣同士を比較するだけ）
• 空間計算量: \(O(N)\)（入力の配列を保持。逐次読みでも書けるが本コードでは配列に保持）

実装のポイント

• 「半分」は小数点以下切り捨てなので、Python では整数除算 D_i // 2 を使う。
• 1曲目は例外的に必ず \(D_1\) 分かかるので、初期値として加えてから \(i=1\)（0-indexなら2曲目）以降を処理すると実装が簡単です。
• 入力が最大 \(2\times 10^5\) なので、sys.stdin.buffer.read() を使うと高速に読めます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    d = data[1:1+n]

    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)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。