Distributed Code Jam 2016 Round 2 : B. again

しょうもないミスでDを落とした。まぁEが解けない時点でFinalの目はないんだけどね。
https://code.google.com/codejam/contest/7244486/dashboard#s=p1

問題

N要素の配列A,Bを処理するあるプログラムが与えられる。
これを高速化せよ。

解法

プログラムを読むと、A[i]*B[j]の、(i+j)%20が0以外の総和を答えるものであることがわかる。
20個のノードを使い、i番のノードでA[20*k+i]及びB[20*k+i]を集計し、それぞれの総和であるSA[i],SB[i]を求めよう。
あとはSA[i],SB[i]を0番のノードに集め、SA[i]*SB[j]のうち(i+j)%20が0以外のものの総和を求めよう。

int TN,MY;
ll N;
ll mo=1000000007;
ll tota[20];
ll totb[20];

void solve(){
	int i,j,k,l,r,x,y; string s;
	N=GetN();
	
	if(MY>=20) return;
	for(i=MY;i<N;i+=20) {
		tota[MY] += GetA(i);
		totb[MY] += GetB(i);
	}
	
	PutLL(0, tota[MY]%mo);
	PutLL(0, totb[MY]%mo);
	Send(0);
	
	if(MY==0) {
		
		FOR(i,20) {
			Receive(i);
			tota[i]=GetLL(i);
			totb[i]=GetLL(i);
		}
		
		ll ret=0;
		FOR(x,20) FOR(y,20) if((x+y)%20!=0) ret += (tota[x]%mo)*(totb[y]%mo)%mo;
		cout<<ret%mo<<endl;
	}
	
}


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

まとめ

まだ簡単。