やっぱり真面目に環境作らないとつらい。
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(); }
まとめ
まあまだ簡単。