JOI2013-2014本選 バウムクーヘン
いまごろですがJOI本選に通過していました。
本選問3バウムクーヘンで配列を2倍にするところを、なぜか2乗の長さが必要だと思い込んでいて解けませんでした。
#include <cstdio> #include <algorithm> using namespace std; #define IDX(a,n,v) distance(a,lower_bound(a,a+n,v)) const int MAXN=100001; int N,A[MAXN*2+1]; long long S[MAXN*2+2], sum; long long INF=1L<<50; bool c(long long len){ for(int i=0;i<N+1;i++){ int j = IDX(S,2*N+1,S[i]+len); if(j>i+N) continue; int k = IDX(S,2*N+1,S[j]+len); if(k>i+N) continue; int l = IDX(S,2*N+1,S[k]+len); if(l<=i+N) return true; } return false; } int main(){ sum=0; scanf("%d",&N); for(int i=0;i<N;i++){ scanf("%d",&A[i]); A[i+N]=A[i]; sum+=A[i]; } S[0]=0; for(int i=1;i<=2*N;i++) S[i]=A[i-1]+S[i-1]; S[2*N+1] = INF; long long h=sum+1, l=0; for(int i=0;i<100;i++){ long long m = (h+l)/2; if(c(m)) l=m; else h=m; } printf("%lld\n", l); return 0; }
数学オリンピックも本選に参加しましたが、こちらは全くできませんでした死。