Codeforces #353 Div2 C. Money Transfers

Cで無駄にタイムロスしたせいで、Eは解法の目途は立っていたのに時間切れ。
http://codeforces.com/contest/675/problem/C

問題

N個の数値A[i]が円周上に並んでおり、その総和は0である。
ある要素から左右どちらかの隣接要素に任意の数だけ数値を移動することを考える。

全要素が0になるには、最小何回数値の移動を行えばよいか。

解法

いくつか解法がある。

まずは自分が本番取った解法を紹介。
Aを幾つかの和の連続部分列A[L..R]の集合(A[N-1]とA[0]は連続と見なす)に分割できたとする。
集合がp個あれば移動回数はN-pなので、できるだけ細かく集合を分けた方が良い。
累積和などを用いA[L]に対応する最短の右端Rを求めるよう。

A[x],A[x+1]...,A[N-1],A[0],...A[x-1]と数列をA[x-1]とA[x]で切り離し、円周上から一直線に並べたとする。
A[L]に対応するRの値を用いて、この数列をいくつの集合に分けられるかを求め、xを総当たりした際の最大値を求めればよい。
集合に分ける数は、ダブリング等用いて高速に求められる。

…と本番はAC出来たもののだいぶ面倒な手間を踏んだ。
もっと簡潔な解法もある。

Aの累積和S[i]=sum(A[0..i])を考える。
iに対し、S[i]=S[j]となる最小のjを考えた時、sum(A[(i+1)..j])は0である。
よって(j-i)回移動を行うと、A[i+1]～A[j]は0に出来るはずである。
またその時S[i]～S[j]はすべて同じ値になる。

言い換えると、S[i]=yとなるようなiの数をf(y)とすると、S[j]=yとなるA[j]以外を動かすようにすると、S[i]はすべてyになり、A[i]が全て0になることに相当する。
その際数値を移動する回数はN-f(y)となる。
よってS[i]の登場回数を求め、f(y)の最大値を求めればN-f(y)が解。

int N;
ll A[201010];
ll S[201010];
map<ll,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
		M[S[i]]++;
	}
	
	int mi=1<<20;
	FORR(r,M) mi=min(mi,N-r.second);
	cout<<mi<<endl;
	
}

まとめ

本番もダブリングなんかDiv2Cじゃでないだろうと思いつつ、ゴリ押ししてしまった。