G - Iroha and Haiku (New ABC Edition) 解説 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")

投稿日時:
最終更新: