ABC265D - Iroha and Haiku (New ABC Edition)

解法：しゃくとり法

考え方

3回のしゃくとり法で，$x = P, Q, R$に対し

• 区間和が$\sum_{[l, r)} A_{l} = x$を満たす$l$の集合$S_{x}$
• $l$を$r$に対応させる辞書$f_{x} (l)=r$

を求めておく．

Yesとなるのは，$l \in S_{P}$

• $f_{P}(l) \in S_{Q}$
• $f_{Q} (f_{P}(l)) \in S_{R}$

を満たすものが存在するとき．

回答例

N, P, Q, R = map(int, input().split())
A = list(map(int, input().split()))

def f(x):
    l, r = 0, 0
    SUM = 0
    l_set = set()
    lr_map = {}
    while r < N:
        while r < N and SUM < x:
            SUM += A[r]
            r += 1
            if SUM == x:
                l_set.add(l)
                lr_map[l] = r
        while l <= r and SUM >= x:
            SUM -= A[l]
            if SUM == x:
                l_set.add(l + 1)
                lr_map[l + 1] = r
            l += 1
        if SUM >= x: break
    return l_set, lr_map

l_set_P, lr_map_P = f(P)
l_set_Q, lr_map_Q = f(Q)
l_set_R, lr_map_R = f(R)

ans = 'No'
for Pl in l_set_P:
    Pr = lr_map_P[Pl]
    if Pr not in l_set_Q: continue
    Qr = lr_map_Q[Pr]
    if Qr not in l_set_R: continue
    exit(print('Yes'))

print(ans)

解法：累積和（+set）

考え方

なるほど！
Submission #34217094 - AtCoder Beginner Contest 265
（【解説 実況】ABC265 AからD【かつっぱ】 - YouTube）