本番は不参加です。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_e
問題
N要素の整数列Aが与えられる。
Aのうち1要素の値を任意に変えられるとする。
Aのうち連続する部分列の総和が0となる数を最小化せよ。
解法
変える要素を決めたら、その値を無限に大きくすれば、その要素を含む部分列は絶対に和が0にならない。
そこで、逆に現状この要素を含む部分列が最も和が0となるケースが多い、という要素を選ぶようにしよう。
Aのprefixの和を考える。
今A[x]を無限大にすることを考える場合、prefixの和がsになるもののうち、長さがx未満の物の数とx以上の物の数の積を取る、ということを全sに行いその和を取ると、A[x]を無限大にしたとき減少する総和0の部分列ということになる。
よって上記総和を求めよう。
毎回愚直にsを総当たりするとO(N^2)かかるが、xを1ずつずらすと前述の値はあまり変化しないので差分だけ考慮していけばよい。
int N; ll A[202020],SA[202020]; map<ll,ll> M,L,R; ll ret; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; M[0]=1; R[0]=0; FOR(i,N) { cin>>A[i]; SA[i+1]=SA[i]+A[i]; ret+=M[SA[i+1]]; M[SA[i+1]]++; L[SA[i+1]]=0; R[SA[i+1]]++; } L[0]=1; ll cur=0; FORR(m,L) cur+=m.second*R[m.first]; ll ma=cur; FOR(i,N-1) { ll a=SA[i+1]; cur-=L[a]*R[a]; L[a]++; R[a]--; cur+=L[a]*R[a]; ma=max(ma,cur); } cout<<ret-ma<<endl; }
まとめ
500ptとしてはちょうどいい問題?