Codeforces #601 Div1 B2. Send Boxes to Alice (Hard Version)

前半にEasy/Hardの分割あんまり置いてほしくないなぁ。キュー詰まりがちだしね。
http://codeforces.com/contest/1254/problem/B2

問題

整数列が与えられる。
時間1を掛けると、ある要素を(負にならない範囲で)1減らし、両脇のどちらかの要素を1増やすことができる。
全体の公約数が2以上になるようにするのにかかる最短時間を求めよ。

解法

まず公約数は整数列の総和の約数である。そこで、総和の素因数を総当たりしよう。
素因数pを定めたら、数列の端から順にみていく。
各要素において、pの倍数からあぶれる分を数えていく。
あぶれる分がpたまったら、それらをその区間の中央に移動させるようにすれば、総移動量が最小になる。

int N;
ll A[1010101];
ll S;
ll mi=1LL<<60;

const int prime_max = 1000000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

bool isprime(ll v) {
	for(ll i=2;i*i<=v;i++) if(v%i==0) return false;
	return (v!=1);
}

ll hoge(ll cand) {
	int i;
	if(cand==1) return 1LL<<60;
	ll ret=0;
	ll sum=0;
	vector<pair<ll,ll>> V;
	FOR(i,N) {
		ll C=A[i];
		ll add=min(C,cand-sum);
		if(add) {
			V.push_back({i,add});
			C-=add;
			sum+=add;
			
			if(sum==cand) {
				ll vc=(cand+1)/2;
				ll mid=0;
				FORR(a,V) {
					if(vc>0 && a.second>=vc) mid=a.first;
					vc-=a.second;
				}
				FORR(a,V) {
					ret+=abs(a.first-mid)*a.second;
				}
				V.clear();
				sum=0;
			}
		}
		
		C%=cand;
		if(C) {
			V.push_back({i,C});
			sum+=C;
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d",&A[i]);
		S+=A[i];
	}
	
	cprime();
	mi=hoge(S);
	FOR(i,NP) if(S%prime[i]==0) mi=min(mi,hoge(prime[i]));
	for(ll a=1;a*a<=S;a++) if(S%a==0 && S/a>=1000000 && isprime(S/a)) mi=min(mi,hoge(S/a));
	
	if(mi==1LL<<60) return _P("-1\n");
	
	cout<<mi<<endl;
	
	
	
	
}

まとめ

総移動量を減らすために真ん中に集めるいつものパターン。