Atcoder 典型90問 076★3[二分探索][累積和]

076 - Cake Cut（★3）

■要約

　問題の流れは理解していたが，実装が難しかったことと，二分探索で条件を満たすRを見つけるという考え方が浮かばなかった．確かに二分探索ならO(logN)で見つけることができるので，こういう使い方もできるかのと勉強になった．

　簡単に問題を解く流れを書くと以下のよう．

①連続するピースを表せるように，ケーキ２周分に配列を拡張する．▶ N番目から数える連続するケーキの組み合わせを表現できる

②累積和Bを求める．

③Br - Bl = Bn/10 となるrを探す旅にでる

N = int(input())
A = list(map(int, input().split()))
import bisect

#円環を2周分の配列として用意
for i in range(N):
 A.append(A[i])

B = [0]*len(A) #累積和を用意
B[0] = A[0]
for i in range(len(A)-1):
 B[i+1] = B[i] + A[i+1]
#print(B)

#10で割り切れなかったらそもそもアウト
if B[N-1] % 10 != 0:
 exit(print("No"))

#目標値
num = B[N-1] // 10

for i in range(N):
 j = bisect.bisect_left(B, num + B[i])
 if B[j] - B[i] == num:
   exit(print("Yes"))
   
print("No")