概要

この問題は、登山道を進みながら標高を変化させていく中で、ちょうど \(1\) 回だけ現在の標高を半分（小数点以下切り捨て）にできる「ロープウェイ」を最適なタイミングで使用し、最終的な標高を最小化する問題です。

考察

1. 素朴なアプローチとその限界

ロープウェイを使用するタイミングは、区間の前後を含めて \(N+1\) 箇所あります。 最も単純な方法は、ロープウェイを使うタイミングをすべて試す（全探索する）ことです。しかし、タイミングを \(1\) つ固定するたびに、最初から最後までシミュレーションを行うと、1回あたり \(O(N)\) の時間がかかります。 全体では \(O(N^2)\) の計算量となり、 \(N \le 5 \times 10^5\) という制約下では実行時間制限（TLE）になってしまいます。

そこで、シミュレーションを高速化するために、「ロープウェイを使うタイミング」の前後で処理を分割して考えるアプローチを取ります。

2. ロープウェイの前後で分けるアイデア

ロープウェイを \(k\) 番目の区間の後（\(k = 0, 1, \ldots, N\)）に使うと固定します（\(k=0\) は最初の区間の前、\(k=N\) は最後の区間の後を意味します）。 このとき、全体のプロセスは以下の3つのステップに分解できます。

1. 前半（区間 \(1\) から \(k\) まで）: ロープウェイを使わずに通常通り進みます。このときの標高を \(h[k]\) とします。
2. ロープウェイの使用: 標高が \(h[k]\) から \(\lfloor h[k] / 2 \rfloor\) に変化します。
3. 後半（区間 \(k+1\) から \(N\) まで）: 変化後の標高 \(X = \lfloor h[k] / 2 \rfloor\) を初期値として、残りの区間を通常通り進みます。

前半の標高 \(h[k]\) は、前から順番にシミュレーションを行うことで、すべての \(k\) について一括して \(O(N)\) で求めることができます。 問題は、「初期値 \(X\) からスタートして、区間 \(k+1\) から \(N\) まで進んだときの最終標高」を各 \(k\) について高速に求められるかという点です。

3. 後半のシミュレーションを高速化する重要な性質

標高が常に \(0\) 以上でなければならない（負になる場合は \(0\) にリセットされる）というルールが、この問題の難しさです。 しかし、初期値 \(X\) からスタートして区間 \(k+1\) から \(N\) まで進んだときの最終標高は、実は次のような非常に綺麗な式で表すことができます。

\[(\text{最終標高}) = \max\left( X + S[k],\ M[k] \right)\]

ここで、 - \(S[k]\) は、区間 \(k+1\) から \(N\) までの変化量 \(D_i\) の総和です。 - \(M[k]\) は、区間 \(k+1\) から \(N\) の途中で標高が \(0\) にリセットされた場合の影響の最大値（空の区間に対する \(0\) も含む）です。具体的には、後ろから累積和をとったときの最大値になります。

なぜこの式が成り立つのか？

途中で一度も標高が \(0\) にリセットされない場合、最終標高は単純に \(X + S[k]\) になります。 一方で、途中のある地点で標高が \(0\) にリセットされた場合、それ以前の標高 \(X\) の影響は完全に消え去り、リセットされた地点からゴールまでの累積変化量だけが最終標高に影響します。 したがって、最終標高は「初期値 \(X\) の影響が残る場合（\(X + S[k]\)）」と「途中で \(0\) にリセットされて、それ以降の変化のみが残る場合（その最大値 \(M[k]\)）」の大きい方になります。

この \(S[k]\) と \(M[k]\) は、後ろから（逆順に）累積和を計算していくことで、すべての \(k\) について一括して \(O(N)\) で求めることができます。

---

アルゴリズム

1. 前方からの累積シミュレーション: 配列 \(h\) を用意します。\(h[0] = 0\) とし、\(i = 1\) から \(N\) まで順に、 $\(h[i] = \max(h[i-1] + D_i,\ 0)\)$ を計算します。これで、ロープウェイを使う前の各時点での標高が求まります。

2. 後方からの累積シミュレーション: 配列 \(S\) と \(M\) を用意します。 後ろ（\(k = N\) から \(1\) まで逆順）に向かってループを回し、区間 \(k\) から \(N\) までの総和 \(S[k-1]\) と、後ろからの累積和の最大値 \(M[k-1]\) を更新していきます。

   • \(S[k-1] = S[k] + D_k\)
   • \(M[k-1] = \max(M[k] + D_k,\ 0)\)

3. 最適なタイミングの探索: \(k = 0, 1, \ldots, N\) のそれぞれについて、ロープウェイを \(k\) 番目の後に使った場合の最終標高 $\(\max\left( \lfloor h[k] / 2 \rfloor + S[k],\ M[k] \right)\)$ を計算し、その最小値を出力します。

---

計算量

• 時間計算量: \(O(N)\) 前方からのシミュレーションに \(O(N)\)、後方からのシミュレーションに \(O(N)\)、最終的な最小値を求める全探索に \(O(N)\) かかります。全体として \(O(N)\) となり、制約の \(N \le 5 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\) 各時点の状態を記録するための配列 \(h, S, M\) を保持するため、 \(O(N)\) のメモリを使用します。

---

実装のポイント

• インデックスの範囲: ロープウェイを使用できる場所は「\(1\) 番目の区間の前（インデックス \(0\)）」から「\(N\) 番目の区間の後（インデックス \(N\)）」までの \(N+1\) 箇所あります。配列のサイズを \(N+1\) で確保し、境界値でのバグ（境界外アクセスなど）が起きないように注意しましょう。

• 切り捨て除算: Python では、// 2 を使うことで自動的に小数点以下を切り捨てた整数（床関数 \(\lfloor \cdot \rfloor\)）を計算できます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    D = [int(x) for x in input_data[1 : N + 1]]

    h = [0] * (N + 1)
    curr_h = 0
    for i in range(N):
        curr_h += D[i]
        if curr_h < 0:
            curr_h = 0
        h[i + 1] = curr_h

    S = [0] * (N + 1)
    M = [0] * (N + 1)

    curr_T = 0
    curr_M = 0
    curr_S = 0

    for k in range(N, 0, -1):
        d = D[k - 1]
        curr_T += d
        curr_S += d
        if curr_T > curr_M:
            curr_M = curr_T
        S[k - 1] = curr_S
        M[k - 1] = curr_M

    ans = 10**18
    for k in range(N + 1):
        val = (h[k] // 2) + S[k]
        if val < M[k]:
            val = M[k]
        if val < ans:
            ans = val

    print(ans)


if __name__ == "__main__":
    solve()

---

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