概要

与えられた数列の中で、「山型」であり、かつ「区間内の最大値と最小値の差が \(K\) 以上」であるような連続する部分区間の最大長を求める問題です。

考察

この問題では、条件を満たす区間を効率よく探す必要があります。\(N\) が最大で \(10^6\) であるため、すべての区間を調べる \(O(N^2)\) のアプローチでは実行時間制限に間に合いません。したがって、\(O(N)\) または \(O(N \log N)\) で解く必要があります。

まず、「山型」の区間に着目します。山型の区間は、ある頂点 \(k\) を持ち、左側に向かって狭義単調減少、右側に向かって狭義単調減少となります。 ある頂点 \(k\) を山の頂点と決め打ったとき、この山型の区間を可能な限り左右に広げることを考えます。左側は「\(H_i < H_{i+1}\)」が続く限り広げられ、右側は「\(H_i > H_{i+1}\)」が続く限り広げられます。これを前計算しておくことで、各 \(k\) に対して最も広い山型の区間を \(O(1)\) で求めることができます。

次に、「最大値と最小値の差が \(K\) 以上」という条件を考えます。 頂点 \(k\) に対応する最も広い山型区間を \([l, r]\) とします。このとき、区間内の最大値は頂点の標高 \(H_k\) です。 また、最小値について考えてみます。左側は左に行くほど標高が低くなり、右側は右に行くほど標高が低くなります。したがって、区間内の最小値は左端の標高 \(H_l\) か、右端の標高 \(H_r\) のどちらか小さい方になります。 つまり、区間の最大値と最小値の差は \(H_k - \min(H_l, H_r)\) です。これが \(K\) 以上になる条件は、\(H_l \leq H_k - K\) または \(H_r \leq H_k - K\) と書けます。

もし、ある頂点 \(k\) を持つ山型区間が条件を満たすなら、最も広い区間 \([l, r]\) が条件を満たすかどうかをチェックすれば十分です。なぜなら、区間を狭めると最大値は変わらないか小さくなり、最小値は大きくなるため、差は小さくなる一方で \(K\) 以上の条件を満たしにくくなるからです。 したがって、すべての頂点 \(k\) について、最も広い山型区間を計算し、それが条件を満たすか確認するだけで、全体の最長区間を見つけることができます。

アルゴリズム

1. 配列 L[i] を計算します。L[i] は \(i\) 番目を右端とする狭義単調増加な連続部分列の最大長です。左から右へ順に、\(H_{i-1} < H_i\) ならば L[i] = L[i-1] + 1、そうでなければ 1 とします。
2. 配列 R[i] を計算します。R[i] は \(i\) 番目を左端とする狭義単調減少な連続部分列の最大長です。右から左へ順に、\(H_i > H_{i+1}\) ならば R[i] = R[i+1] + 1、そうでなければ 1 とします。
3. 各 \(i\) を山の頂点と仮定し、最も広い山型区間の左端 li = i - L[i] + 1 と右端 ri = i + R[i] - 1 を求めます。
4. 区間の最小値は \(\min(H[li], H[ri])\) です。条件 \(H[li] \leq H[i] - K\) または \(H[ri] \leq H[i] - K\) を満たす場合、区間の長さ L[i] + R[i] - 1 を候補として最大値を更新します。
5. 全ての \(i\) を調べた後、最大の長さを出力します。

計算量

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

実装のポイント

• 「区間内の最小値は左端か右端のどちらか」という点に気付くことが、この問題を線形時間で解くための鍵です。山型の性質上、端に近づくほど標高が低くなるため、わざわざセグメント木などで区間最小値を求める必要はありません。

• Pythonなどの遅い言語では、入力を sys.stdin.readline で受け取ることで入力のオーバーヘッドを減らし、実行時間制限に間に合わせるようにします。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    L = [1] * N
    for i in range(1, N):
        if H[i-1] < H[i]:
            L[i] = L[i-1] + 1
            
    R = [1] * N
    for i in range(N-2, -1, -1):
        if H[i] > H[i+1]:
            R[i] = R[i+1] + 1
            
    ans = 0
    for i in range(N):
        li = i - L[i] + 1
        ri = i + R[i] - 1
        if H[li] <= H[i] - K or H[ri] <= H[i] - K:
            length = L[i] + R[i] - 1
            if length > ans:
                ans = length
                
    print(ans)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。