kmjp's blog

競技プログラミング参加記です

Distributed Code Jam 2017 Round 2 : B. flagpoles

やっぱり真面目に環境作らないとつらい。
https://code.google.com/codejam/contest/3284486/dashboard#s=p1

問題

数列が与えられる。
この連続部分列のうち、最長の等差数列の要素数を求めよ。

解法

数列をノード数個に等間隔で分割しよう。
各ノードでは分割内での最長数列を求めるほか、両隣のノードの数列と連結するため、先頭2要素を含む最長数列および末尾2要素を含む最長数列の長さ・初項・公差を求め、1つのノードに集めよう。
集めた先のノードで、隣接ノード間の結果を可能な範囲でくっつけていけばよい。

int TN,MY;

ll N;
ll H[10101000];

void slow() {
	int i,j,k,l,r,x,y; string s;
	if(MY!=0) return;
	
	FOR(i,N) H[i]=GetHeight(i);
	
	int ma=1;
	x=0;
	while(x<N-1) {
		ll D=H[x+1]-H[x];
		y=x+2;
		while(y<N && H[y]-H[y-1]==D) y++;
		ma=max(ma,y-x);
		x=y-1;
	}
	cout<<ma<<endl;
	
	
}

void fast() {
	int i,j,k,l,r,x,y; string s;
	
	ll L=N*MY/TN;
	ll R=N*(MY+1)/TN;
	ll W=R-L;
	FOR(i,W) H[i]=GetHeight(L+i);
	
	int ma=1;
	x=0;
	while(x<W-1) {
		ll D=H[x+1]-H[x];
		y=x+2;
		while(y<N && H[y]-H[y-1]==D) y++;
		ma=max(ma,y-x);
		x=y-1;
	}
	
	ll LD=H[1]-H[0];
	ll RD=H[W-1]-H[W-2];
	int LS,RS;
	for(LS=1;LS<W;LS++) {
		if(H[LS]-H[LS-1]!=LD) break;
	}
	for(RS=1;RS<W;RS++) {
		if(H[W-RS]-H[W-RS-1]!=RD) break;
	}
	
	PutInt(0,ma);
	PutLL(0,W);
	PutLL(0,H[0]);
	PutLL(0,LD);
	PutLL(0,LS);
	PutLL(0,H[W-1]);
	PutLL(0,RD);
	PutLL(0,RS);
	Send(0);
	
	if(MY!=0) return;
	
	ll LDS[101],RDS[101],LH[101],RH[101],LSS[101],RSS[101],WS[101];
	ma=0;
	FOR(i,TN) {
		Receive(i);
		ma=max(ma,GetInt(i));
		WS[i]=GetLL(i);
		LH[i]=GetLL(i);
		LDS[i]=GetLL(i);
		LSS[i]=GetLL(i);
		RH[i]=GetLL(i);
		RDS[i]=GetLL(i);
		RSS[i]=GetLL(i);
	}
	
	FOR(i,TN) {
		if(i==0) {
			x=RSS[0];
		}
		else {
			if(RDS[i-1]==LDS[i] && RH[i-1]+RDS[i-1]==LH[i]) {
				x+=LSS[i];
				ma=max(ma,x);
				if(LSS[i]==WS[i]) continue;
			}
			x=RSS[i];
		}
	}
	
	
	cout<<ma<<endl;
	
}

void solve(){
	
	N=GetNumFlagpoles();
	if(N<=10100) slow();
	else fast();
}

まとめ

まあまだ簡単。