ABC384 D問題
解説みたけど理解できませんでした...。
なので、私のような数学が苦手な人でも理解できるよう解説します。
部分ごとに考える
まず、部分ごとに分けて考えましょう。
入力例１を例に挙げると、以下のように分けられます。
この繰り返しの部分は今回の場合８から始まっており、8,4,3を繰り返しています。
この部分は、繰り返しの開始の数字が何であっても、
繰り返した回数×配列Ａの総和になります
今回は、8,4,3を２回繰り返しているので15 × 2で３０になっています。
もし、3から始まり、これを二回繰り返していたとしても、
3,8,4を二回繰り返すので、15 × 2で30になります。
では、これが何を意味するかと言うと、今回の問題で考えるべきは、
sとAの総和の余り
のみということになります。
なぜなら、繰り返しの部分の値は常に一定になるからです。
なので、その値にAの部分和を足し、sの値にすることに集中できます。
n,s = map(int,input().split())
a = list(map(int,input().split()))
find_num = s % sum(a)
find_numはsとAの総和の余りです。
今回の問題は、言い換えると「Aの部分列の総和==find_numを探す」です。
累積和を取ろう
Aの範囲の総和なので累積和を取りましょう。
a *= 2
rui = [0] * (n * 2)
tmp = 0
for i in range(2 * n):
rui[i] = a[i] + tmp
tmp += a[i]
累積和を取ったため、rui[j] - rui[i]の値がfind_numかどうかで判定が出来ます。
では、なぜ二倍の累積和を取ったかというと、
入力１ではAの入力は、n = 3 , s = 42 , a = [3,8,4]でしたが、
もし、sの値が37だとしたら、s%sum(a)=7なので、3と4を選ばなければ答えは出ません。
無限数列なので、3と4は、二週目以降4,3の順番で繋がります。
そのため、その時の判定もするために二倍のサイズで累積和を取りました。
rui[j] - rui[i]の値を求めまくろう。
ここまで来たら、あとは条件を満たす値を探索するだけです。
求め方はたくさんありますが、私の求め方を紹介します。
ans = "No"
l = 0
r = 0
while(r < 2 * n):
now = rui[r] - rui[l]
#小さかったらrを増やして広げる
if(now < find_num):
r += 1
#大きかったらlを増やして縮める
elif(now > find_num):
l += 1
#同じだったら正解だ
elif(now == find_num):
ans = "Yes"
break
やっていることは、見ての通りです。
あとがき
初投稿です。
ここまで見てくださり、ありがとうございました。
拙い部分も多くあったと思います。
コメントなどでご指摘・ご質問などございましたらお気軽にしてください。