第13回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#C - バームクーヘン (Baumkuchen)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #C - バームクーヘン (Baumkuchen) https://atcoder.jp/contests/joi2014ho/tasks/joi2014ho3 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll n; cin>>n; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } vector<ll> b(n*3); for(ll i=0;i<n;i++){ b[i]=b[n+i]=b[2*n+1]=a[i]; } b.emplace(b.begin(),0); partial_sum(b.begin(),b.end(),b.begin()); auto cal=[&](ll x){ for(ll i=0;i<n;i++){ ll j=i; j=lower_bound(b.begin()+j,b.end(),b[j]+x)-b.begin(); j=lower_bound(b.begin()+j,b.end(),b[j]+x)-b.begin(); j=lower_bound(b.begin()+j,b.end(),b[j]+x)-b.begin(); if(j-i<=n){ return 1; } } return 0; }; ll ans=0,num=accumulate(a.begin(),a.end(),0LL); while(ans+1<num){ ll m=(ans+num)>>1; if(cal(m)){ ans=m; }else{ num=m; } } cout<<ans<<endl; return 0; }