通過したのでオンサイトです。去年のFHCもそうだし、こういう解法易実装力本質一発AC難みたいなコンテストはオンラインジャッジ勢にとっては一番希望がありますね。
事前準備とか
今年はある程度は真面目に対策しました。
やったこと
- ちゃんと環境が動いているか確認する (MinGWを使った)
- わざわざ使い方を他の場所で調べなくても良いように、コードの雛形を作成
#include<stdio.h> #include<algorithm> #include<message.h> #include"QUESTION NAME HERE.h" using namespace std; /* USER'S GUIDE Num of data / node: 1000 Amount of data / node: 8MB HOW TO USE TOO COMPLICATED AND TOO DIFFICULT LIBRARIES python dcj/dcj.py test --source QUESTIONNAME.cpp --nodes NUMBER_OF_NODES FUNCTION LIBRARIES : int NumberOfNodes(); int MyNodeId(); void PutChar(int target, char value); void PutInt(int target, int value); void PutLL(int target, long long value); void Send(int target); : call this after using Put*** int Receive(int source); call this before using Get*** (return value: number of sended values) char GetChar(int source); int GetInt(int source); long long GetLL(int source); */ int main(){ }
- 過去問のうち正解者が1人以上いる問題の解法の確認
R1に出て得た教訓もあります。
各問題
A:
既出。解決不能。
B:
mod 20ごとに分けて云々。有名問題。
long long mod=1000000007; long long A[30]; long long B[30]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetN(); long long L=(long long)I*N/T; long long R=(long long)(I+1)*N/T; for(int i=L;i<R;i++){ A[i%T]+=GetA(i); B[i%T]+=GetB(i); } for(int i=0;i<20;i++){ A[i]%=mod; B[i]%=mod; } if(I){ for(int i=0;i<T;i++){ PutLL(0,A[i]); PutLL(0,B[i]); } Send(0); }else{ for(int i=1;i<T;i++){ Receive(i); for(int j=0;j<T;j++){ A[j]+=GetLL(i); B[j]+=GetLL(i); } } for(int i=0;i<T;i++){ A[i]%=mod; B[i]%=mod; } long long sa=0; long long sb=0; for(int i=0;i<T;i++){ sa=(sa+A[i])%mod; sb=(sb+B[i])%mod; } long long ret=sa*sb%mod; for(int i=0;i<T;i++){ ret=(ret+mod-A[i]*B[(T-i)%T]%mod)%mod; } printf("%lld\n",ret); } }
C:
括弧の対応の様子を+1,-1にして折れ線グラフにする。有名問題。
各区間での下方向に飛び出す深さとその深さに最初になる場所、その区間全体での深さの変化を計算する。
あとはノード0から順にデータを隣に流していってダメになったところを見つける。
答えがNになるケースを忘れてて1WA。
int p[10100000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetLength(); long long L=(long long)I*N/T; long long R=(long long)(I+1)*N/T; p[0]=L; int at=0; int rm=0; for(int i=L;i<R;i++){ char c=GetCharacter(i); if(c=='(')at--; else at++; if(rm<at){ p[at]=i+1; rm=at; } } int st=0; if(I){ Receive(I-1); st=GetInt(I-1); if(st<0){ if(I<T-1){ PutInt((I+1)%T,-114514); Send((I+1)%T); } return 0; } } if(st-rm<0){ printf("%d\n",p[st+1]-1); if(I<T-1){ PutInt((I+1),-114514); Send((I+1)); } }else{ st-=at; if(I<T-1){ PutInt((I+1)%T,st); Send((I+1)%T); }else{ if(st)printf("%d\n",N); else printf("-1\n"); } } }
D:
去年のOnline C (https://code.google.com/codejam/contest/8254486/dashboard#s=p2)と全く同じ方針でDPを並列化する。
上下方向に薄くスライスして、それぞれは左から少しずつ計算しては途中までの結果を上に伝えていく。
結構危ない実装をしている。
char str[320][31000]; int SQ=300; int dp[320][31000]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int H=GetHeight(); int W=GetWidth(); T=min(T,H); if(I>=T)return 0; int L=H*I/T; int R=H*(I+1)/T; for(int i=L;i<R;i++){ for(int j=0;j<W;j++){ str[i-L][j]=GetPosition(i,j); } } for(int j=0;j<W;j++)str[R-L][j]='0'; int BL=(W+SQ-1)/SQ; for(int i=0;i<320;i++)for(int j=0;j<31000;j++)dp[i][j]=-9999999; for(int i=0;i<BL;i++){ if(I){ Receive(I-1); for(int j=SQ*i;j<SQ*(i+1)&&j<W;j++){ int t=GetInt(I-1); if(str[0][j]!='#')dp[0][j]=max(dp[0][j],t+str[0][j]-'0'); } }else{ for(int j=SQ*i;j<SQ*(i+1)&&j<W;j++){ if(str[0][j]!='#')dp[0][j]=str[0][j]-'0'; } } for(int j=0;j<R-L;j++){ for(int k=SQ*i-j;k<SQ*(i+1)+j;k++){ if(k<0||k>=W)continue; if(str[j+1][k]!='#')dp[j+1][k]=max(dp[j+1][k],dp[j][k]+str[j+1][k]-'0'); if(k&&str[j][k-1]!='#'&&str[j+1][k-1]!='#')dp[j+1][k-1]=max(dp[j+1][k-1],dp[j][k]+str[j][k-1]-'0'+str[j+1][k-1]-'0'); if(k<W-1&&str[j][k+1]!='#'&&str[j+1][k+1]!='#')dp[j+1][k+1]=max(dp[j+1][k+1],dp[j][k]+str[j][k+1]-'0'+str[j+1][k+1]-'0'); } } if(I<T-1){ if(i){ for(int j=SQ*(i-1);j<SQ*i;j++){ PutInt(I+1,dp[R-L][j]); } Send(I+1); } if(i==BL-1){ for(int j=SQ*i;j<W;j++){ PutInt(I+1,dp[R-L][j]); } Send(I+1); } } } if(I==T-1){ int ret=-9999999; for(int i=0;i<W;i++)ret=max(ret,dp[R-L][i]); if(ret<-999)printf("-1\n"); else printf("%d\n",ret); } }
E:
結局スライド最小値になる。有名問題。
これも区間に分けて、容量が大きくて長い区間の最小値を求めたいときは、事前計算で常にスライドされる中に入っているブロックの最小値を別に求めておいてminをとると。dequeに出し入れされる要素の個数は(区間の長さ)*2くらいになる
dequeはメモリ使用量が大きいのでメモリに無駄がないようにする(無駄に配列に持たない、とか)。
int mv[200]; int main(){ int T=NumberOfNodes(); int I=MyNodeId(); int N=GetNumKms(); int D=GetTankSize(); long long L=(long long)N*I/T; long long R=(long long)N*(I+1)/T; int mm=1000000007; for(int i=L;i<R;i++){ mm=min(mm,(int)(GetGasPrice(i))); } mv[I]=mm; for(int i=0;i<T;i++){ if(i==I)continue; PutInt(i,mm); Send(i); } for(int i=0;i<T;i++){ if(i==I)continue; Receive(i); mv[i]=GetInt(i); } int wa=max(0LL,L-D); int wb=max(0LL,R-D); int zm=0; for(int i=0;i<T;i++){ if((long long)N*(i+1)/T>wa){ zm=i;break; } } //printf("%d\n",zm); int F=(long long)N*zm/T; int G=min((long long)L,(long long)N*(zm+2)/T); int ks=1000000007; for(int i=zm+2;i<I;i++){ ks=min(ks,mv[i]); } deque<pair<int,int> > Q; long long ret=0; for(int i=F;i<G;i++){ if(i<=L-D)continue; int ii=GetGasPrice(i); if(i>=R-D){ ks=min(ks,ii); continue; } while(Q.size()&&Q.back().first>=ii){ Q.pop_back(); } Q.push_back(make_pair(ii,i)); } for(int i=L;i<R;i++){ int ii=GetGasPrice(i); while(Q.size()&&Q.back().first>=ii){ Q.pop_back(); } Q.push_back(make_pair(ii,i)); while(Q.front().second<=i-D){ Q.pop_front(); } ret+=min(ks,Q.front().first); } //printf("%lld %lld: %lld\n",L,R,ret); if(I){ PutLL(0,ret); Send(0); }else{ for(int i=1;i<T;i++){ Receive(i); ret+=GetLL(i); } printf("%lld\n",ret); } }
Result:
全部通って100点、5位でした。
去年のOnline Roundは1点だったので、1年間で点数が100倍になったことになります。このままのペースでいくと、10年後には10000000000000000000000点になります。
