076 - Cake Cut（★3）

・問題URL

https://atcoder.jp/contests/typical90/tasks/typical90_bx

・発想

・輪になってんのうざいから直線にしたれ。ってのは思いついたけど、前は二分探索知らなくて無理だった。

・解法

ケーキを直線にして同じのもう一個つなげると「連続するピース」が扱いやすい。（別に３個以上連続してもその区間は答えにならないから、３個以上つなげてもいい。）次に、小数は危険なので全部のピースを10倍して前から累積和を出す。累積和の配列をＡとすると、rep(i,2*N)でＡ[i+1]~A[2N-1]の中に(ケーキの大きさ)-A[i]があるかをbinary_searchで求めればおけ。

・コード

int main(){

 ll N;
 cin>>N;
 vector<ll>A(2*N),sum(2*N);
 rep(i,N){
   cin>>A[i];
   A[N+i]=A[i];
 }
 ll SUM=0;
 rep(i,N)SUM+=A[i];
 rep(i,2*N){
   A[i]*=10;
 }
 ll cake=0;
 rep(i,2*N){
   cake+=A[i];
   sum[i]=cake;
 }
 

 bool Q=binary_search(sum.begin(),sum.end(),SUM);
 for(int i=1;i<2*N;i++){
   if(Q)break;
   Q=binary_search(sum.begin()+i,sum.end(),SUM+sum[i-1]);
 }

 if(Q)cout<<"Yes"<<endl;
 else cout<<"No"<<endl;

}