TopCoder SRM 683 Div1 Easy MoveStones

Easyはさっくりとけ、Mediumはなんとか解いてレート微増。
https://community.topcoder.com/stat?c=problem_statement&pm=14174

問題

N個の石の山が円周上に並んでおり、順にA[i]個ずつ積まれている。
石を1個ずつ隣の山に移す、という作業を繰り返し、各山の石の数をB[i]にしたい。
必要な作業回数の最小値を求めよ。

解法

Aの総和とBの総和が異なるときはどうやっても条件を満たせないので、そのケースは先にコーナーケースとして除外する。
以後sum(A)==sum(B)とする。

作業回数が最小のケースでは、隣接する山のうち、その間でやり取りが発生しない箇所がある。
よってそのような箇所を総当たりしよう。
円周上で考えると面倒だが、i番と(i+1)番の山で石のやり取りが発生しないとすると、C=A[(i+1)..(N-1)]+A[0..(i-1)]、D=B[(i+1)..(N-1)]+B[0..(i-1)]と置くと、CをDにする問題と還元できる。
こうすると円周で考える必要がなくなる。

後は端から順に決めていこう。
前述のとおりC[i]をD[i]にしたいとき、C[i]＞D[i]なら余分のC[i]-D[i]個の石をC[i+1]に渡し、C[i]＜D[i]なら足りないD[i]-C[i]個の石をC[i+1]からもらう、という処理を各iに繰り返せばよい。
処理過程でC[i]が一時的にマイナスになっても問題ない。

class MoveStones {
	public:
	long long get(vector <int> a, vector <int> b) {
		ll SA=0,SB=0;
		int N;
		int i,j;
		N=a.size();
		
		FORR(r,a) SA+=r;
		FORR(r,b) SB+=r;
		if(SA!=SB) return -1;
		ll mi=1LL<<60;
		FOR(i,N) {
			vector<ll> A,B;
			FOR(j,N) A.push_back(a[(i+j)%N]);
			FOR(j,N) B.push_back(b[(i+j)%N]);
			
			ll pat=0;
			FOR(j,N-1) {
				A[j+1]+=A[j]-B[j];
				pat+=abs(A[j]-B[j]);
			}
			mi=min(mi,pat);
			
		}
		return mi;
	}
}

まとめ

類題を見たことあったので迷わず解けた。