概要

\(N\) 人が一列に並び、各人がボールを右に投げたとき、最初に自分より身長が高い人がキャッチします。各転送のコスト（投げた人からキャッチした人までの区間の身長の最小値）の合計を効率的に求める問題です。

考察

問題の整理

\(i\) 番目の人が投げたボールについて、以下の2つを求める必要があります：

1. キャッチする人 \(j\)：\(i\) より右側で、\(H_j > H_i\) を満たす最も左の人
2. 転送コスト：区間 \([i, j]\) の身長の最小値 \(\min(H_i, H_{i+1}, \ldots, H_j)\)

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

各 \(i\) について、右方向に順に走査して \(j\) を見つけ、さらに区間の最小値を求めると、最悪 \(O(N^2)\) の時間がかかり、\(N \leq 2 \times 10^5\) では TLE になります。

効率化の方針

2つのサブ問題をそれぞれ高速に解きます：

1. Next Greater Element（次の大きい要素）：単調スタックを使うと全体で \(O(N)\) で求められます。
2. 区間最小値クエリ（Range Minimum Query）：Sparse Table を前処理 \(O(N \log N)\) で構築すれば、各クエリを \(O(1)\) で処理できます。

具体例

\(H = [3, 1, 4, 1, 5]\) の場合：

• \(i=0\)（身長3）→ 右で最初に3より大きいのは \(j=2\)（身長4）→ コスト \(= \min(3,1,4) = 1\)
• \(i=1\)（身長1）→ \(j=2\)（身長4）→ コスト \(= \min(1,4) = 1\)
• \(i=2\)（身長4）→ \(j=4\)（身長5）→ コスト \(= \min(4,1,5) = 1\)
• \(i=3\)（身長1）→ \(j=4\)（身長5）→ コスト \(= \min(1,5) = 1\)
• \(i=4\) → キャッチする人なし → コスト \(= 0\)
• 合計 \(= 1+1+1+1+0 = 4\)

アルゴリズム

Step 1: Sparse Table の構築

配列 \(H\) に対して Sparse Table を構築します。\(\text{sparse}[k][i] = \min(H[i], H[i+1], \ldots, H[i+2^k-1])\) を前計算しておくことで、任意の区間 \([l, r]\) の最小値を \(O(1)\) で求められます。

\[\text{query\_min}(l, r) = \min(\text{sparse}[k][l],\ \text{sparse}[k][r - 2^k + 1])\]

ここで \(k = \lfloor \log_2(r - l + 1) \rfloor\) です。

Step 2: 単調スタックで Next Greater Element を求める

左から右へ走査しながら、スタックに「まだ次の大きい要素が見つかっていないインデックス」を保持します。スタックは \(H\) の値について単調減少に保ちます。

新しい要素 \(H[j]\) を見るたびに、スタックの先頭の要素 \(H[\text{top}]\) と比較し、\(H[\text{top}] < H[j]\) ならば \(j\) が \(\text{top}\) の Next Greater Element です。

Step 3: コストの合計

各 \(i\) について Next Greater Element \(j\) が存在すれば、\(\text{query\_min}(i, j)\) を合計に加算します。

計算量

• 時間計算量: \(O(N \log N)\)（Sparse Table の構築に \(O(N \log N)\)、Next Greater Element に \(O(N)\)、各クエリに \(O(1) \times N\) 回）
• 空間計算量: \(O(N \log N)\)（Sparse Table の格納）

実装のポイント

• 単調スタックの条件：H[stack[-1]] < H[j]（厳密に小さい）でポップします。等しい場合はキャッチしないため、等号を含めないよう注意が必要です。

• Sparse Table のサイズ：\(\log_2 N\) の計算には N.bit_length() を利用すると簡潔に書けます。

• \(H[j] > H[i]\) であるため、区間 \([i, j]\) の最小値は実質 \(\min(H[i], H[i+1], \ldots, H[j-1])\) と同じですが、\(H[j]\) を含めても結果は変わらないため、そのまま \([i, j]\) 全体で最小値を取って問題ありません。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    H = [int(input_data[i+1]) for i in range(N)]
    
    # For each i, find j = next greater element (strictly greater) to the right
    # Cost = min(H[i], H[i+1], ..., H[j])
    # Since H[j] > H[i], the min of range [i, j] is min(H[i], H[i+1], ..., H[j-1])
    # which equals min(H[i], min(H[i+1..j-1]))
    # But we need an efficient way to compute this.
    
    # Step 1: Find next greater element for each i using a stack
    # Step 2: Compute range minimum queries efficiently using sparse table
    # Step 3: Sum up the costs
    
    # Build sparse table for range minimum queries
    import math
    if N == 0:
        print(0)
        return
    
    LOG = max(1, N.bit_length())
    sparse = [None] * LOG
    sparse[0] = H[:]
    
    for k in range(1, LOG):
        length = 1 << k
        prev = sparse[k-1]
        cur = [0] * N
        for i in range(N - length + 1):
            cur[i] = min(prev[i], prev[i + (1 << (k-1))])
        sparse[k] = cur
    
    def query_min(l, r):
        # min of H[l..r] inclusive
        if l > r:
            return float('inf')
        length = r - l + 1
        k = length.bit_length() - 1
        return min(sparse[k][l], sparse[k][r - (1 << k) + 1])
    
    # Find next greater element using monotonic stack
    # Stack stores indices in decreasing order of H values
    total = 0
    stack = []  # stack of indices, monotonically decreasing in H value
    
    # Process from right to left
    # For each i, we want the smallest j > i such that H[j] > H[i]
    # Using a stack processed left to right:
    
    # Actually, let's process left to right with a stack that helps find next greater
    # Standard next greater element: process left to right, maintain stack of indices
    # whose next greater hasn't been found yet. Stack is monotonically decreasing.
    
    nge = [-1] * N  # next greater element index, -1 if none
    stack = []
    
    for j in range(N):
        while stack and H[stack[-1]] < H[j]:
            i = stack.pop()
            nge[i] = j
        stack.append(j)
    
    # Now compute total cost
    total = 0
    for i in range(N):
        j = nge[i]
        if j == -1:
            continue
        # cost = min(H[i..j])
        total += query_min(i, j)
    
    print(total)

main()

---

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