Distributed Code Jam 2016 Round 1 : D. crates

ローカルデバッグ環境無しで良く通ったな…。
https://code.google.com/codejam/contest/11264486/dashboard#s=p3

問題

N要素の数列H[i]がある。
ある要素から、隣の要素に値を1動かす、ということを繰り返し、全値を平均化したい。
(全体を同じ値に出来ない場合、手前の要素が1多くなるようにしたい)

最小何回移動を行えばよいか。

解法

分散処理を行わない場合は典型問題である。
H[i]の総和を求めると、そこから各要素の処理後の値A[i]が決まる。
後は先頭から順にH[i]をA[i]にしていき、その際不足分は後の要素から借りる・過剰分は後の要素に押し出す、ということを行えばよい。
この過程では一時的にH[i]が負になっても構わない。

これを分散処理できるようにしよう。
まずH[i]及びA[i]をノードP個に均等に分割してブロックに分ける。
ブロック内のH[i]の和とA[i]の和を求めると、前述の要領で後ろのブロックから借りる・押し出す量が定まる。

これで各ブロックから借りる・押し出す量が定まるので、あとは各ノードでその分を踏まえたうえでブロック内の借りる・押し出す量を求めればよい。

int TN,MY;

ll N;
ll H[1010100];
ll A[1010100];
ll mo=1000000007;
ll TS[101];
ll TA[101];

void solve(){
	int i,j,k,l,r,x,y; string s;
	
	N=GetNumStacks();
	if(N<=3*TN) {
		if(MY!=0) return;
		ll sum=0;
		FOR(i,N) H[i]=GetStackHeight(i+1), sum+=H[i];
		FOR(i,N) A[i]=sum/N + (i<(sum%N));
		
		ll tot=0;
		FOR(i,N-1) {
			tot += abs(A[i]-H[i]);
			H[i+1] += H[i]-A[i];
			tot %= mo;
		}
		cout<<tot<<endl;
	}
	else {
		int step=(N+TN-1)/TN;
		int st=step*MY;
		int ed=min(step*(MY+1),(int)N);
		
		ll mysum=0;
		for(i=st;i<ed;i++) mysum += GetStackHeight(i+1);
		PutLL(0,mysum);
		Send(0);
		
		ll sum=0;
		ll ret=0;
		if(MY==0) {
			FOR(i,TN) {
				Receive(i);
				TS[i] = GetLL(i);
				sum += TS[i];
			}
			FOR(i,TN) {
				int st1=step*i;
				int ed1=min(step*(i+1),(int)N);
				TA[i] = sum/N*(ed1-st1);
				if(st1<sum%N) TA[i] += min(sum%N,(ll)ed1)-st1;
			}
			FOR(i,TN-1) {
				ret += abs(TS[i]-TA[i]);
				TS[i+1] += TS[i]-TA[i];
				PutLL(i+1,sum);
				PutLL(i+1,TS[i]-TA[i]);
				Send(i+1);
			}
		}
		
		ll delta = 0;
		if(MY!=0) {
			Receive(0);
			sum = GetLL(0);
			delta = GetLL(0);
		}
		for(i=st;i<ed-1;i++) {
			ll cur = GetStackHeight(i+1) + delta;
			ll tar = sum/N + (i<(sum%N));
			ret += abs(tar-cur);
			delta = cur-tar;
			ret %= mo;
		}
		if(MY!=0) {
			PutLL(0,ret);
			Send(0);
		}
		else {
			for(i=1;i<TN;i++) {
				Receive(i);
				ret += GetLL(i);
			}
			cout<<ret%mo<<endl;
		}
		
		
		
	}
	
}


int main(int argc,char** argv){
	
	TN=NumberOfNodes();
	MY=MyNodeId();
	solve();
	return 0;
	
}

まとめ

流石にEはローカル環境無しではキツかった。
後で復習できないのが辛いな。