Atcoder 典型90問 076★3[二分探索][累積和]
見出し画像

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

■要約

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

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

①連続するピースを表せるように,ケーキ2周分に配列を拡張する.▶ 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")
この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
岐阜▶大阪大学院生 普段は群ロボットの研究をしたり,画像処理して遊んでます. Atcoderを始めたものの計算量という概念が無知すぎてで沈没しているので個人的な勉強用として置いていきます.