Distributed Code Jam 2017 Round 1 : B. pancakes

E-largeはツメが甘くてWA。ただそれ以外は相変わらず環境が悪いながらも解ききった。
https://code.google.com/codejam/contest/8314486/dashboard#s=p1

問題

1～Dの順で人が円形に並んでいる。
この人たちに、パンケーキの山を配って回る。
パンケーキのうち上からi番目はS[i]番の人のためのものである。

給仕は円をぐるぐる回りつつ、山の一番上にあるパンケーキに対応する人の前に来るとそのパンケーキを渡す。
(そのようなパンケーキが複数枚あれば、1度に複数枚渡す)

山のパンケーキを渡しきるまで、給仕は何周配って回る必要があるか。

解法

S[i]＞S[i+1]であるような数を求めればよい。
各ノードでSを等分に分割し、それぞれの結果を足し合わせるだけ。

int TN,MY;

ll S;
int D;

void slow() {
	int i,j,k,l,r,x,y; string s;
	if(MY!=0) return;
	
	int pre=1<<30;
	int cnt=0;
	FOR(i,S) {
		x=GetStackItem(i);
		if(x<pre) cnt++;
		pre=x;
	}
	
	if(MY==0) {
		cout<<cnt<<endl;
	}
}

void fast() {
	int i,j,k,l,r,x,y; string s;
	
	int L=S*MY/TN;
	int R=S*(MY+1)/TN;
	
	int pre=1<<30;
	int cnt=0;
	if(L>0) pre=GetStackItem(L-1);
	
	for(i=L;i<R;i++) {
		x=GetStackItem(i);
		if(x<pre) cnt++;
		pre=x;
	}
	
	PutInt(0,cnt);
	Send(0);
	
	if(MY==0) {
		int ret=0;
		FOR(i,TN) {
			Receive(i);
			ret+=GetInt(i);
		}
		cout<<ret<<endl;
	}
}

まとめ

まぁまだ1問目なので簡単。