Please sign in first.
G - Iroha and Haiku (New ABC Edition) Editorial
by
Tomii9273
尺取法を利用した解法です。
\(S(l, r) := A_l + A_{l+1} + \cdots + A_{r-1}\)
とします。ここで、
\(Y(x) := (S(x, y) ≥ P を満たす最小のy, 無い場合は n) \)
\(Z(x) := (S(Y(x), z) ≥ Q を満たす最小のz, 無い場合は n) \)
\(W(x) := (S(Z(x), w) ≥ R を満たす最小のw, 無い場合は n) \)
とすると、条件を満たす可能性のある区切り方は \((x, Y(x), Z(x), W(x)) (x = 0, 1, 2, \cdots , n-1)\) に限られます。
\(x\) を増加させたとき、\(Y(x), Z(x), W(x)\) はいずれも (広義) 単調増加するため、尺取法を利用して区切りと区間和を管理することで、全ての区切り方 \((x, Y(x), Z(x), W(x))\) の決定と判定が \(O(N)\) で可能になります。
実装例
n, p, q, r = map(int, input().split())
A = list(map(int, input().split()))
y, z, w = 0, 0, 0
s0, s1, s2 = 0, 0, 0
ok = 0
for x in range(n):
while y < n and s0 < p:
s0 += A[y]
s1 -= A[y]
y += 1
while z < n and s1 < q:
s1 += A[z]
s2 -= A[z]
z += 1
while w < n and s2 < r:
s2 += A[w]
w += 1
if s0 == p and s1 == q and s2 == r:
ok = 1
break
s0 -= A[x]
print("Yes" if ok else "No")
posted:
last update: