概要

この問題は、山登りの途中でちょうど 1 回だけロープウェイ（現在の標高を \(\lfloor h / 2 \rfloor\) にする）を使用するとき、最終的な標高を最小化する問題です。

ロープウェイを使用するタイミングは \(N+1\) 通りあります。それぞれのタイミングについて、それ以降の標高の推移を高速にシミュレーションすることで、全体として時間計算量 \(O(N)\) で解くことができます。

---

考察

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

ロープウェイを使用するタイミングを \(j\) 番目の区間の後（\(j = 0, 1, \ldots, N\)）と固定してみます。 このとき、最終的な標高を求めるには以下の手順を踏むことになります。

1. 最初から \(j\) 番目の区間までは、通常通りに登る。
2. \(j\) 番目の区間の後でロープウェイを使い、標高を半分にする。
3. そこから \(N\) 番目の区間まで通常通りに登る。

このシミュレーションを各 \(j\) について愚直に行うと、1回あたり \(O(N)\) の計算量がかかります。タイミングは \(N+1\) 通りあるため、全体の計算量は \(O(N^2)\) となり、 \(N \le 5 \times 10^5\) という制約下では実行時間制限（TLE）になってしまいます。

したがって、「ロープウェイを使った後の挙動」を \(O(1)\) で高速に計算する必要があります。

2. 標高の遷移の性質（「0未満にならない」の言い換え）

標高の遷移は \(h \leftarrow \max(h + D_i, 0)\) と表されます。この「\(0\) 未満になったら \(0\) にリセットされる」という操作には、非常に便利な性質があります。

初期値 \(x\) からスタートして、変化量 \(D_1, D_2, \ldots, D_k\) を順に適用したときの最終的な値を考えてみましょう。 途中で一度も \(0\) にリセットされない場合は、単に \(x + \sum D_i\) となります。しかし、途中で \(0\) にリセットされる場合、最後に \(0\) にリセットされた位置を \(m\) とすると、それ以降は一度も \(0\) にリセットされずにゴールに到達するため、最終的な値は \(\sum_{i=m+1}^k D_i\) となります。

実は、この「途中で \(0\) にリセットされる」という挙動を含めた最終的な値は、「すべてのリセット位置の候補（リセットしない場合も含む）からスタートしたときの、単純な累積和の最大値」と一致します。

具体例

初期値 \(x = 10\) で、変化量が \([-20, +5]\) の場合を考えます。 - 愚直なシミュレーション： 1. 初期値: \(10\) 2. \(1\) 番目の区間後: \(\max(10 - 20, 0) = 0\) 3. \(2\) 番目の区間後: \(\max(0 + 5, 0) = 5\) 最終的な標高は \(5\) です。

• 最大値をとる方法：
  1. 一度もリセットされない場合（初期値 \(10\) からスタート）: \(10 - 20 + 5 = -5\)
  2. \(1\) 番目の区間の後でリセットされた場合（初期値 \(0\) からスタート）: \(0 + 5 = 5\)
  3. \(2\) 番目の区間の後でリセットされた場合（初期値 \(0\) からスタート）: \(0\) これらの最大値は \(\max(-5, 5, 0) = 5\) となり、シミュレーション結果と一致します。

この性質を利用すると、ロープウェイを使用した直後の標高を \(x\) としたとき、そこからゴールまでの最終的な標高は、以下の2つの最大値として表せます。

1. 一度も \(0\) にリセットされない場合: $\(x + (\text{区間 } j+1 \text{ から } N \text{ までの変化量の総和})\)$
2. 途中で少なくとも 1 回 \(0\) にリセットされる場合: $\(\max_{m=j+1}^N (\text{区間 } m+1 \text{ から } N \text{ までの変化量の総和})\)\( （※ \)m=N\( のときは空の和となり \)0$ になります）

この2つの値は、事前に「後ろからの累積和」を計算しておくことで、任意の \(j\) に対して \(O(1)\) で取得可能になります。

---

アルゴリズム

以下の3つの配列を前計算します。

1. 配列 \(h\) （前から通常通りに登ったときの標高）

   • \(h[i]\) : 区間 \(1\) から \(i\) まで通常通りに登った直後の標高。
   • 遷移: \(h[i] = \max(0, h[i-1] + D_i)\)　（ただし \(h[0] = 0\)）

2. 配列 \(A\) （後ろからの単純な累積和）

   • \(A[i]\) : 区間 \(i\) から \(N\) までの変化量の総和。
   • \(A[i] = A[i+1] + D_i\)　（ただし \(A[N+1] = 0\)）

3. 配列 \(B\) （後ろからの累積和の最大値）

   • \(B[i]\) : 区間 \(i\) 以降の「ある位置からゴールまでの累積和」の最大値。
   • \(B[i] = \max(A[i+1], B[i+1])\)　（ただし \(B[N+1] = 0\)）

ロープウェイを \(j\) 番目の区間の後に使う場合

ロープウェイ使用直後の標高は \(h'_j = \lfloor h[j] / 2 \rfloor\) です。 このとき、最終的な標高は以下の式で \(O(1)\) で求まります。 $\(\text{val} = \max( h'_j + A[j+1], B[j+1] )\)$

すべての \(j = 0, 1, \ldots, N\) についてこの値を計算し、その最小値が答えとなります。

---

計算量

• 時間計算量: \(O(N)\) 配列 \(h\) の計算（前方向への走査）に \(O(N)\)、配列 \(A, B\) の計算（後ろ方向への走査）に \(O(N)\)、そしてロープウェイを使用する位置 \(j\) の全探索に \(O(N)\) かかります。全体として線形時間で動作します。

• 空間計算量: \(O(N)\) 長さ \(N+2\) の配列をいくつか保持するため、空間計算量は \(O(N)\) です。

---

実装のポイント

• オーバーフローの防止: 標高の変化量 \(D_i\) は最大で \(10^9\)、最小で \(-10^9\) であり、累積和は 32 ビット整数の範囲を超える可能性があります。そのため、C++ では long long 型（Python では標準の整数型）を使用する必要があります。

• インデックスの境界: \(j = 0\)（1番目の区間の前）や \(j = N\)（\(N\) 番目の区間の後）などの境界条件で配列の範囲外にアクセスしないよう、配列のサイズを \(N+2\) に確保し、適切に初期化（A[N+1] = 0, B[N+1] = 0）しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> D(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> D[i];
    }

    vector<long long> h(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        h[i] = max(0LL, h[i - 1] + D[i]);
    }

    vector<long long> A(N + 2, 0);
    vector<long long> B(N + 2, 0);
    for (int i = N; i >= 1; --i) {
        A[i] = A[i + 1] + D[i];
        B[i] = max(A[i + 1], B[i + 1]);
    }

    long long min_val = -1;
    bool first = true;

    for (int j = 0; j <= N; ++j) {
        long long h_prime = h[j] / 2;
        long long val = max(h_prime + A[j + 1], B[j + 1]);
        if (first || val < min_val) {
            min_val = val;
            first = false;
        }
    }

    cout << min_val << "\n";

    return 0;
}

---

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