概要

\(N\) 曲のピアノ練習曲を順番に演奏する際、特定の条件（直前の曲より難易度が高い）を満たす場合に演奏時間が半分になるというルールのもと、全曲を演奏するのにかかる合計時間を求める問題です。

考察

この問題で最も重要なのは、「ある曲の演奏時間が、その直前の曲の難易度のみに依存する」という点です。

具体的には、 \(i\) 番目の曲（ \(i \ge 2\) ）の演奏時間は以下の条件で決まります。

• \(D_{i-1} < D_i\) のとき： \(D_i / 2\) 分（小数点以下切り捨て）
• \(D_{i-1} \ge D_i\) のとき： \(D_i\) 分

最初の曲（ \(D_1\) ）については比較対象がないため、常に \(D_1\) 分かかります。

このルールは非常にシンプルで、前の曲の状態（それまでに何曲連続で難易度が上がっていたかなど）を気にする必要はありません。したがって、配列を先頭から順番に見ていき、隣り合う要素を比較するだけで合計時間を計算できます。

制約を確認すると、曲数 \(N\) は最大 \(2 \times 10^5\) 、難易度 \(D_i\) は最大 \(10^9\) です。

• \(N\) が大きいため、二重ループなどを用いる \(O(N^2)\) の解法では実行時間制限（TLE）に間に合いませんが、一度の走査で済む \(O(N)\) の解法であれば十分に間に合います。
• 合計時間は \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\) 程度になる可能性があるため、大きな数値を扱える型（Pythonでは自動的に対応されます）を使用する必要があります。

アルゴリズム

1. 合計時間を保持する変数 total_time を用意し、最初の曲の難易度 \(D_1\) で初期化します。
2. 2番目の曲から \(N\) 番目の曲まで、順番に以下の処理を繰り返します。
   • 現在の曲の難易度 \(D_i\) と、一つ前の曲の難易度 \(D_{i-1}\) を比較します。
   • もし \(D_{i-1} < D_i\) ならば、 total_time に \(D_i // 2\) （切り捨て除算）を加算します。
   • そうでなければ、 total_time に \(D_i\) をそのまま加算します。
3. 最終的な total_time の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の要素を一度だけ順番に確認するため、曲数 \(N\) に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の難易度をリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 切り捨て除算: Pythonでは // 演算子を使うことで、整数同士の割り算の結果を小数点以下切り捨て（整数）で取得できます。
• インデックスの範囲: ループを回す際、 \(i=0\) （1番目）は初期値として使い、 \(i=1\) から \(N-1\) までを比較対象とするように範囲を設定します。
• 大きな数値の入力: sys.stdin.read().split() を使うことで、大量の入力データを高速に読み込むことができます。

ソースコード

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 曲の数 N
    n = int(input_data[0])
    # 各曲の難易度 D_1, D_2, ..., D_N
    d = list(map(int, input_data[1:]))
    
    # 最初の曲は比較対象がないため、必ず D_1 分かかる
    total_time = d[0]
    
    # 2番目以降の曲について計算
    for i in range(1, n):
        # 直前の曲より難易度が高い場合、かかる時間は半分（切り捨て）
        if d[i] > d[i-1]:
            total_time += d[i] // 2
        else:
            # そうでない場合はそのままの難易度分の時間がかかる
            total_time += d[i]
            
    # 合計時間を出力
    print(total_time)

if __name__ == '__main__':
    solve()

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