E - 花壇の区間選び / Choosing Flowerbed Intervals Editorial by admin
gemini-3.5-flash-thinking概要
この問題は、長さ \(N\) の花壇の連続する区間 \([l, r]\) のうち、以下の 2 つの条件を同時に満たすものの個数を求める問題です。
- 条件 1（品種の多様さ）: 区間内の（異なる品種の数 \(D\)）\(\times\)（区間の長さ \(r - l + 1\)）\(\le K\)
- 条件 2（高さのバランス）: 区間内の（最大高さ）\(-\)（最小高さ）\(\le M\)
制約が \(N \le 2 \times 10^5\) と大きいため、すべての区間を個別に調べると \(O(N^2)\) 以上の時間がかかり実行時間制限に間に合いません。 この解説では、区間の「単調性」に注目し、尺取り法（Two Pointers）とスライド最大値・最小値（deque）を組み合わせて \(O(N)\) で解く方法を解説します。
考察
単調性の活用
右端 \(r\) を固定したとき、左端 \(l\) を右に動かして区間 \([l, r]\) を縮めていくことを考えます。
条件 1 について 区間を縮めると、区間の長さ \((r - l + 1)\) は必ず減少します。また、含まれる品種の種類数 \(D\) も減少するか変化しません。 したがって、値 \(D \times (r - l + 1)\) は \(l\) を大きくするにつれて単調に減少（または不変）します。 よって、ある \(r\) に対して条件 1 を満たす最小の左端を \(l_1\) とすると、任意の \(l \ge l_1\) について条件 1 を満たします。
条件 2 について 区間を縮めると、区間内の最大値は減少または不変、最小値は増加または不変となります。 したがって、最大値と最小値の差は \(l\) を大きくするにつれて単調に減少（または不変）します。 よって、ある \(r\) に対して条件 2 を満たす最小の左端を \(l_2\) とすると、任意の \(l \ge l_2\) について条件 2 を満たします。
求める区間の数
右端 \(r\) を固定したとき、両方の条件を同時に満たす左端 \(l\) の範囲は、 $\(\max(l_1, l_2) \le l \le r\)\( となります。このような \)l\( の個数は、 \)\text{limit} = \max(l_1, l_2)\( とおくと、 \)\text{limit} \le r\( のときに \)r - \text{limit} + 1$ 個存在します。
さらに、右端 \(r\) を右に進めたとき、条件を満たすために必要な左端の下限 \(l_1\) および \(l_2\) は、それぞれ右にしか進みません（単調非減少）。 この性質を利用して、右端 \(r\) を動かしながら、左端のポインタ \(l_1, l_2\) を尺取り法の要領で管理することができます。
アルゴリズム
右端 \(r\) を \(0\) から \(N-1\) まで順番に進めながら、以下の処理を行います。
1. 条件 2（高さのバランス）の管理：ポインタ \(l_2\)
区間内の最大値・最小値を効率よく取得するために、スライド最大値・最小値（deque を用いた手法）を使用します。
max_dq: 区間内の要素のインデックスを、値が降順になるように保持する両端キュー。min_dq: 区間内の要素のインデックスを、値が昇順になるように保持する両端キュー。
新しい要素 \(B[r]\) を追加する際、キューの末尾から \(B[r]\) より「最大値/最小値として不適切な要素」を取り除いてから \(r\) を追加します。
その後、B[max_dq[0]] - B[min_dq[0]] > M（現在の最大値と最小値の差が \(M\) を超えている）である限り、左端 \(l_2\) を右に進めます。このとき、キューの先頭にあるインデックスが \(l_2\) より小さくなればキューから削除します。
2. 条件 1（品種の多様さ）の管理：ポインタ \(l_1\)
区間 \([l_1, r]\) に含まれる各品種の出現回数を配列 cnt で、異なる品種の数を変数 \(D\) で管理します。
- \(A[r]\) を追加し、新しく登場した品種であれば \(D\) を \(1\) 増やします。
- \(D \times (r - l_1 + 1) > K\) である限り、左端 \(l_1\) を右に進めます。進める際、取り除く要素 \(A[l_1]\) の出現回数を \(1\) 減らし、出現回数が \(0\) になったら \(D\) を \(1\) 減らします。
3. 答えの集計
各 \(r\) において、条件を満たす左端の最小値は \(\text{limit} = \max(l_1, l_2)\) です。 \(\text{limit} \le r\) であれば、区間の個数 \(r - \text{limit} + 1\) を答えに加算します。
計算量
時間計算量: \(O(N)\)
- 右端のポインタ \(r\) は \(0\) から \(N-1\) まで \(1\) ずつ増加します。
- 左端のポインタ \(l_1\) と \(l_2\) も、それぞれ最大で \(N\) 回しか右に進みません。
dequeへの要素の追加・削除は、各要素について高々 \(1\) 回ずつしか行われません。- したがって、すべての操作が全体で \(O(N)\) で行われます。
空間計算量: \(O(N)\)
- 品種の出現回数を記録する配列
cnt（サイズ \(N+1\)）と、最大値・最小値を管理するdeque（最大サイズ \(N\)）を使用するため、空間計算量は \(O(N)\) です。
- 品種の出現回数を記録する配列
実装のポイント
インデックスの管理:
dequeには値そのものではなく「インデックス」を格納します。これにより、左端 \(l_2\) が進んだときに、キューの先頭要素が現在の区間外（max_dq[0] < l2）になったかどうかを定数時間で判定できます。オーバーフローへの注意: 条件 1 の判定式 \(D \times (r - l_1 + 1)\) は、最大で約 \(N^2 \approx 4 \times 10^{10}\) に達します。Python では自動的に多倍長整数として扱われますが、C++ などの他言語で実装する場合は、計算途中でオーバーフローを防ぐために 64 ビット整数型（
long longなど）を使用してください。ソースコード
import sys
from collections import deque
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
K = int(data[1])
M = int(data[2])
A = [int(x) for x in data[3:3+N]]
B = [int(x) for x in data[3+N:3+2*N]]
# 条件2 (高さのバランス) を管理するための deque とポインタ
max_dq = deque()
min_dq = deque()
l2 = 0
# 条件1 (品種の多様さ) を管理するための頻度配列とポインタ
cnt = [0] * (N + 1)
D = 0
l1 = 0
ans = 0
for r in range(N):
# 条件2の更新 (B[r] を追加)
br = B[r]
while max_dq and B[max_dq[-1]] <= br:
max_dq.pop()
max_dq.append(r)
while min_dq and B[min_dq[-1]] >= br:
min_dq.pop()
min_dq.append(r)
# 高さの差が M 以下になるまで l2 を進める
while B[max_dq[0]] - B[min_dq[0]] > M:
l2 += 1
if max_dq[0] < l2:
max_dq.popleft()
if min_dq[0] < l2:
min_dq.popleft()
# 条件1の更新 (A[r] を追加)
ar = A[r]
if cnt[ar] == 0:
D += 1
cnt[ar] += 1
# D * (r - l1 + 1) <= K を満たすまで l1 を進める
while D * (r - l1 + 1) > K:
al1 = A[l1]
cnt[al1] -= 1
if cnt[al1] == 0:
D -= 1
l1 += 1
# 両方の条件を満たす左端の下限
limit = l1 if l1 > l2 else l2
if limit <= r:
ans += r - limit + 1
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。
posted:
last update: