みんなO(N log N)で解いているらしいですが工夫してひたすら実装してメモリ削るとBFSするだけで解けます。
基本的な方針は、まず盤面(だいたい100000*100000くらいだと思っておく)を100*100のセルたちに分割して、その中に叙位君の歩いた軌跡があるかどうかで場合わけ。
叙位君が歩いたセルは(どうせN/100くらいしかありません)それぞれ辺を全部ひいてBFSします。すると分割された場所の面積とどんなかんじにつながっているかが分かります。それぞれの分割に番号をつけて、この番号の領域から外に出られるのはどの端(100の長さのが4つ)から出られるか、それからここから入ってくるとどの番号の領域に当てられるか。を持っておきます。
あとは自明に図形の外側になるところからBFS。適当に場合わけすれば全部のマスにBFSすることができます。
最初投げたら70%でしたが、ソースを眺めていたら1箇所if(0<=NR+dx[m]&&NR+dx[m]<100&&0<=NC+dy[m]&&NC+dy[m]<100&&!(kabe[NR][NC]略をif(0<=NR+dx[m]&&NR+dx[m]<100&&0<=NC+dx[m]&&NC+dx[m]<100&&!(kabe[NR][NC]略にタイプミスしていたことが分かり、直したらACしました。こういうミス本番で絶対にやりたくないけど対策の仕様がないのが難点。こわすぎ
#include<stdio.h> #include<algorithm> #include<queue> #include<vector> using namespace std; char str[100001]; char in[2]; pair<int,int>J[100001]; pair<int,int>C[100001]; vector<int>A[1010][1010]; vector<int>B[1010][1010]; int V[1010][1010]; int ban[101][101]; short conv[2500][400]; vector<vector<int > >D[2500]; vector<int>has[2500]; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; int kabe[101][101]; int vis[1010][1010]; pair<int,int>rev[2500]; vector<int> vis2[2500]; int main(){ int now=0; while(1){ scanf("%s",in); if(in[0]=='Q')break; str[now++]=in[0]; } int row=0; int col=0; int nowJ=0; int nowC=0; for(int i=0;i<now;i++){ switch(str[i]){ case 'N': C[nowC++]=make_pair(row++,col); break; case 'S': C[nowC++]=make_pair(--row,col); break; case 'E': J[nowJ++]=make_pair(row,col++); break; case 'W': J[nowJ++]=make_pair(row,--col); break; } } int MR=0; int MC=0; for(int i=0;i<nowC;i++){ MR=min(MR,C[i].first); MC=min(MC,C[i].second); } for(int i=0;i<nowJ;i++){ MR=min(MR,J[i].first); MC=min(MC,J[i].second); } MR=-MR+110; MC=-MC+110; //printf("%d %d\n",MR,MC); int num=0; for(int i=0;i<1010;i++) for(int j=0;j<1010;j++) V[i][j]=-1; for(int i=0;i<nowC;i++){ C[i].first+=MR; C[i].second+=MC; if(C[i].second%100==0){ A[C[i].first/100][C[i].second/100-1].push_back(i); if(!~V[C[i].first/100][C[i].second/100-1])V[C[i].first/100][C[i].second/100-1]=num++; A[C[i].first/100][C[i].second/100].push_back(i); if(!~V[C[i].first/100][C[i].second/100])V[C[i].first/100][C[i].second/100]=num++; }else{ A[C[i].first/100][C[i].second/100].push_back(i); if(!~V[C[i].first/100][C[i].second/100])V[C[i].first/100][C[i].second/100]=num++; } } for(int i=0;i<nowJ;i++){ J[i].first+=MR; J[i].second+=MC; if(J[i].first%100==0){ B[J[i].first/100-1][J[i].second/100].push_back(i); if(!~V[J[i].first/100-1][J[i].second/100])V[J[i].first/100-1][J[i].second/100]=num++; B[J[i].first/100][J[i].second/100].push_back(i); if(!~V[J[i].first/100][J[i].second/100])V[J[i].first/100][J[i].second/100]=num++; }else{ B[J[i].first/100][J[i].second/100].push_back(i); if(!~V[J[i].first/100][J[i].second/100])V[J[i].first/100][J[i].second/100]=num++; } } queue<pair<int,int> > Q; for(int i=0;i<1010;i++){ for(int j=0;j<1010;j++){ if(~V[i][j]){ rev[V[i][j]]=make_pair(i,j); for(int k=0;k<101;k++){ for(int l=0;l<101;l++){ ban[k][l]=-1; kabe[k][l]=0; } } for(int k=0;k<A[i][j].size();k++){ if(C[A[i][j][k]].second>j*100)kabe[C[A[i][j][k]].first-i*100][C[A[i][j][k]].second-j*100-1]|=4; if(C[A[i][j][k]].second<(j+1)*100)kabe[C[A[i][j][k]].first-i*100][C[A[i][j][k]].second-j*100]|=8; } for(int k=0;k<B[i][j].size();k++){ if(J[B[i][j][k]].first>i*100)kabe[J[B[i][j][k]].first-i*100-1][J[B[i][j][k]].second-j*100]|=1; if(J[B[i][j][k]].first<(i+1)*100)kabe[J[B[i][j][k]].first-i*100][J[B[i][j][k]].second-j*100]|=2; } int n=0; for(int k=0;k<100;k++){ for(int l=0;l<100;l++){ if(ban[k][l]==-1){ Q.push(make_pair(k,l)); ban[k][l]=n; while(Q.size()){ int NR=Q.front().first; int NC=Q.front().second; Q.pop(); for(int m=0;m<4;m++){ if(0<=NR+dx[m]&&NR+dx[m]<100&&0<=NC+dy[m]&&NC+dy[m]<100&&!(kabe[NR][NC]&(1<<m))&&!~ban[NR+dx[m]][NC+dy[m]]){ ban[NR+dx[m]][NC+dy[m]]=n; Q.push(make_pair(NR+dx[m],NC+dy[m])); } } } n++; } // printf("%d ",kabe[k][l]); } // printf("\n"); } // printf("%d\n",n); has[V[i][j]]=vector<int>(n); vis2[V[i][j]]=vector<int>(n); for(int k=0;k<100;k++) for(int l=0;l<100;l++) has[V[i][j]][ban[k][l]]++; D[V[i][j]]=vector<vector<int> > (n); for(int l=0;l<100;l++){ conv[V[i][j]][l]=ban[0][l]; if(!(kabe[99][l]&1))D[V[i][j]][ban[99][l]].push_back(l); } for(int l=0;l<100;l++){ conv[V[i][j]][l+300]=ban[l][99]; if(!(kabe[l][0]&8))D[V[i][j]][ban[l][0]].push_back(l+300); } for(int l=0;l<100;l++){ conv[V[i][j]][l+100]=ban[99][l]; if(!(kabe[0][l]&2))D[V[i][j]][ban[0][l]].push_back(l+100); } for(int l=0;l<100;l++){ conv[V[i][j]][l+200]=ban[l][0]; if(!(kabe[l][99]&4))D[V[i][j]][ban[l][99]].push_back(l+200); } } } } long long ret=10201000000LL; vis[0][0]=1; Q.push(make_pair(0,0)); ret-=10000; while(Q.size()){ int NR=Q.front().first; int NC=Q.front().second; Q.pop(); if(NR<0){ NR=-(NR+1); int H1=rev[NR].first; int H2=rev[NR].second; for(int i=0;i<D[NR][NC].size();i++){ int y=H1+dx[D[NR][NC][i]/100]; int z=H2+dy[D[NR][NC][i]/100]; if(~V[y][z]){ if(!vis2[V[y][z]][conv[V[y][z]][D[NR][NC][i]]]){ vis2[V[y][z]][conv[V[y][z]][D[NR][NC][i]]]=1; ret-=has[V[y][z]][conv[V[y][z]][D[NR][NC][i]]]; Q.push(make_pair(-1-V[y][z],conv[V[y][z]][D[NR][NC][i]])); } }else{ if(!vis[y][z]){ vis[y][z]=1; ret-=10000; Q.push(make_pair(y,z)); } } } }else{ for(int i=0;i<4;i++){ int y=NR+dx[i]; int z=NC+dy[i]; if(0<=y&&y<1010&&0<=z&&z<1010){ if(~V[y][z]){ if(!vis2[V[y][z]][conv[V[y][z]][i*100]]){ vis2[V[y][z]][conv[V[y][z]][i*100]]=1; Q.push(make_pair(-V[y][z]-1,conv[V[y][z]][i*100])); ret-=has[V[y][z]][conv[V[y][z]][i*100]]; } }else{ if(!vis[y][z]){ vis[y][z]=1; ret-=10000; Q.push(make_pair(y,z)); } } } } } } printf("%lld\n",ret); }
メモリ61MBとか使いましたが多分2500を小さくすればまだ何とかなります。
