九州大学プログラミングコンテスト2018 : E - Treeone

本番は不参加です。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_e

問題

N要素の整数列Aが与えられる。
Aのうち１要素の値を任意に変えられるとする。
Aのうち連続する部分列の総和が０となる数を最小化せよ。

解法

変える要素を決めたら、その値を無限に大きくすれば、その要素を含む部分列は絶対に和が０にならない。
そこで、逆に現状この要素を含む部分列が最も和が０となるケースが多い、という要素を選ぶようにしよう。

Aのprefixの和を考える。
今A[x]を無限大にすることを考える場合、prefixの和がsになるもののうち、長さがx未満の物の数とx以上の物の数の積を取る、ということを全sに行いその和を取ると、A[x]を無限大にしたとき減少する総和０の部分列ということになる。

よって上記総和を求めよう。
毎回愚直にsを総当たりするとO(N^2)かかるが、xを１ずつずらすと前述の値はあまり変化しないので差分だけ考慮していけばよい。

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としてはちょうどいい問題？