概要

\(N\) 個の区間を通過する登山で、ちょうど1回ロープウェイ（標高を半分に切り捨て）を使う最適なタイミングを求め、最終標高を最小化する問題。全 \(N+1\) 箇所の候補を効率的に評価する。

考察

素朴なアプローチの問題点

各ロープウェイ使用位置 \(k\) について、前半 \(k\) 区間を処理し、標高を半分にし、残りの \(N-k\) 区間を処理すると \(O(N)\) かかるため、全体で \(O(N^2)\) となりTLEになる。

重要な気づき：後半処理の関数形

区間 \(k+1\) 〜 \(N\) を開始標高 \(s\) から処理した最終標高を \(f_k(s)\) とする。この関数には以下の性質がある：

\[f_k(s) = \max(s + S_k,\ L_k)\]

ここで： - \(S_k\)：区間 \(k+1\) 〜 \(N\) の \(D_i\) の合計（クランプが起きない場合の純変化量） - \(L_k = f_k(0)\)：開始標高 \(0\) から処理した場合の最終標高

なぜこの形になるか： 1. \(f_k(s)\) は \(s\) について非減少で、傾きは \(0\) か \(1\) のみ 2. \(s\) が十分大きければクランプ（\(0\) への切り上げ）が発生せず、\(f_k(s) = s + S_k\) 3. \(s\) が小さいとどこかでクランプされ、結果は \(f_k(0) = L_k\) に一致 4. クランプにより標高は上がるだけなので、常に \(f_k(s) \geq s + S_k\)

結果として、\(f_k(s) = \max(s + S_k, L_k)\) が成り立つ。

アルゴリズム

1. 前方計算：\(h\_prefix[k]\) = 最初の \(k\) 区間を処理した後の標高を \(O(N)\) で計算

2. 後方計算：右から左へ \(O(N)\) で以下を計算

   • \(suffix\_sum[k]\)：\(D[k] + D[k+1] + \cdots + D[N-1]\)
   • \(suffix\_f0[k]\)：標高 \(0\) から区間 \(k\) 〜 \(N-1\) を処理した最終標高

漸化式： $\(suffix\_f0[i] = \max(\max(D[i], 0) + suffix\_sum[i+1],\ suffix\_f0[i+1])\)$

1. 各候補の評価：ロープウェイを位置 \(k\)（\(0 \leq k \leq N\)）で使う場合の最終標高： $\(\text{final}(k) = \max\left(\left\lfloor \frac{h\_prefix[k]}{2} \right\rfloor + suffix\_sum[k],\ suffix\_f0[k]\right)\)$

2. 全 \(k\) について最小値を取る。

具体例

\(D = [-3, 10, -5]\) の場合： - \(suffix\_sum = [2, 5, -5, 0]\)、\(suffix\_f0 = [5, 5, 0, 0]\)（\(f(0)\) from start = 5） - \(k=0\)：\(s = 0\)、\(\max(0+2, 5) = 5\) - \(k=1\)：\(h\_prefix[1]=0\), \(s=0\)、\(\max(0+5, 5) = 5\) - \(k=2\)：\(h\_prefix[2]=10\), \(s=5\)、\(\max(5-5, 0) = 0\) - \(k=3\)：\(h\_prefix[3]=5\), \(s=2\)、\(\max(2+0, 0) = 2\)

最小値は \(0\)（\(k=2\) が最適）。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• suffix_f0 の漸化式では、\(f_k(s) = \max(s + S, L)\) の公式を再帰的に利用している。標高 \(0\) から区間 \(i\) を通過すると \(\max(D[i], 0)\) になり、そこから残りの区間の関数を適用する。

• Python では整数の // 演算子は負の方向に丸めるが、\(h\_prefix[k] \geq 0\) が保証されるため問題ない。

• 入力が大きいので sys.stdin.buffer.read() で高速に読み込む。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    D = [int(input_data[i+1]) for i in range(N)]
    
    # Compute prefix heights (before ropeway)
    # h[0] = 0, h[i] = max(h[i-1] + D[i-1], 0) for i=1..N
    # We can use ropeway at position k (0 <= k <= N), meaning:
    #   - First process sections 1..k to get height h[k]
    #   - Apply ropeway: h[k] -> floor(h[k] / 2)
    #   - Then process sections k+1..N to get final height
    
    # Precompute h[k] for k=0..N (height after first k sections, no ropeway)
    h_prefix = [0] * (N + 1)
    for i in range(N):
        h_prefix[i+1] = max(h_prefix[i] + D[i], 0)
    
    # Now we need: given starting height s after ropeway, process sections k+1..N
    # The height evolution with floor-to-0: h = max(h + D[i], 0)
    # 
    # For sections k+1..N, the final height as a function of starting height s is:
    # f_k(s) = result of processing sections k+1..N starting from s
    # f_k(s) is a piecewise linear non-decreasing function of s (slope 0 or 1)
    # 
    # Key insight: f_k(s) = max(s + suffix_sum_from_{k+1}, min_suffix_prefix_from_{k+1})
    # Actually, let's think more carefully.
    #
    # For processing sections i=k+1..N from starting height s:
    # The result is max(s + S[k+1..N], -min over j in [k+1..N] of partial sums that would go below 0...)
    # 
    # Actually: f(s) = max(s + total_suffix, max over all suffixes of partial negative sums)
    # 
    # Let me think differently. Define for sections k+1..N:
    # Let cumulative sum from position k+1: C[j] = D[k+1] + D[k+2] + ... + D[j] for j >= k+1, C[k] = 0
    # The height after section j is: max over all "resets" at 0.
    # 
    # f(s) = max(s + C_total, -min_{j} (something))
    # 
    # This is equivalent to: for a sequence of operations, f(s) = max(s + sum_all, L)
    # where L = max over j in {k+1,...,N} of (C[j..N] - C[j-1..N]) considering resets...
    #
    # Actually: f(s) = max(s + S, L) where S is the total sum of D[k+1..N] and 
    # L is the final height starting from 0.
    # No that's not right either because of the max with 0 nonlinearity.
    #
    # f(s) for the sequence is: max(s + S, L) where L = f(0) and S = net sum when no clamping occurs.
    # This IS correct because clamping at 0 means f(s) = s + S when s is large enough that no clamping happens,
    # and f(s) = f(0) = L when s is small enough. The threshold is where s + min_prefix = 0.
    # So f(s) = max(s + S, L).
    
    # Compute suffix_sum[k] = D[k] + D[k+1] + ... + D[N-1] and suffix_f0[k] = f(0) for sections k..N-1
    # f(s) for sections k..N-1 = max(s + suffix_sum[k], suffix_f0[k])
    
    suffix_sum = [0] * (N + 1)  # suffix_sum[k] = sum of D[k..N-1]
    suffix_f0 = [0] * (N + 1)   # f(0) for sections k..N-1, i.e., height starting from 0
    
    # Build from right to left
    # suffix_sum[N] = 0, suffix_f0[N] = 0
    for i in range(N - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i+1] + D[i]
        # Starting from 0, apply section i: h = max(0 + D[i], 0) = max(D[i], 0)
        # Then apply sections i+1..N-1: f_{i+1}(h)
        h_after_i = max(D[i], 0)
        suffix_f0[i] = max(h_after_i + suffix_sum[i+1], suffix_f0[i+1])
    
    ans = float('inf')
    for k in range(N + 1):
        s = h_prefix[k] // 2  # floor(h/2)
        # Process sections k..N-1 starting from s
        final = max(s + suffix_sum[k], suffix_f0[k])
        if final < ans:
            ans = final
    
    print(ans)

solve()

---

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