ABC384Dを解いた【累積和】

筆者はレート800前後の茶～緑コーダ

ABC384当日にACできなかったD問題を解いていく

実装コード

求める値Sは数列1周分の総和で剰余を取ればいいらしい、
そして2週分の累積和で該当する数を探すようだ。

探し方はS[i]=Sもしくは
S[j]-S[i]=Sを移項して
S[j]=S+S[i]となる数を探すようだ

main.py

import sys
from itertools import accumulate
from bisect import bisect_left
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)



def main():
    N, X = rLI()
    A = rLI()
    B = A+A
    S = set(accumulate(B))
    M = X%sum(A)
    for s in sorted(S):
        if s == M or s+M in S:
            print("Yes")
            break
    else:   
        print("No")
        
if __name__ == '__main__':
    main()

まとめ

累積和を出す発想はあったが
剰余を取るのと2週分まで累積和をとるという発想が難しかった。

もっと柔軟に解けるようになりたい