なんかえらく苦戦してるな。
http://codeforces.com/contest/1358/problem/E
問題
N要素の整数列Aが与えられる。
うち後半半分は同じ値Xであることがわかっている。
Aのうち任意の位置のK要素の連続部分列の総和が正であるようなKを1つ求めよ。
解法
- Aの総和が正ならK=Nが解となる。
- そうでない場合、X≧0の場合前半のマイナスが大きすぎるので解はない。
- 残りはAの総和が0以下でXも負の場合である。
その場合、各左端について右端をどこまで伸ばせるかを考えよう。
L(i) := i番目の要素を左端とする部分列のうち、総和が正を満たせる最長の長さ
R(i) := min(L(0),....,L(i))
とする。Xは負なので、L(i)は上限がある。
あとは、i+R(i)≧NとできるR(i)があればそれが解となる。
int N; ll A[505050]; ll X; ll S[505050]; int ML[505050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,(N+1)/2) cin>>A[i]; cin>>X; FOR(i,N-(N+1)/2) A[(N+1)/2+i]=X; FOR(i,N) S[i+1]=S[i]+A[i]; if(S[N]>0) { cout<<N<<endl; return; } if(X<0) { int len=(N+1)/2; for(i=0;i<(N+1)/2;i++) { if(S[i+len]-S[i]<=0) break; int mlen=min((ll)N-i,len+(S[i+len]-S[i]-1)/(-X)); ML[i]=mlen; if(i) ML[i]=min(ML[i],ML[i-1]); if(i+ML[i]>=N) { cout<<ML[i]<<endl; return; } } } cout<<-1<<endl; }
まとめ
最終的なコードは短いけど、途中結構コーナーケースで苦労した。