AOJ 1355: L∞ Jumps
ir5さんが解説をslideshareに上げている。
本質は使う移動と移動するときのコストの基準点(1になるところ)の対応がGreedyというか両方同じ順であるということで、それが分かっていれば方向全探索O(N^3)、始点O(N)、内部でGreedyがO(N)で解けるという感じ。
4方向系の問題はどうしてもこういう実装になってしまう。コピペミスしていてかなり時間がかかった。
#include<stdio.h> #include<algorithm> using namespace std; long long x[100]; long long y[100]; long long r[100]; int main(){ int n; scanf("%d",&n); long long d,s,t; scanf("%lld%lld%lld",&d,&s,&t); for(int i=0;i<n;i++){ scanf("%lld%lld",x+i,y+i); if(y[i]==-d)r[i]=x[i]+d; else if(x[i]==d)r[i]=2*d+y[i]+d; else if(y[i]==d)r[i]=4*d-x[i]+d; else r[i]=6*d-y[i]+d; } for(int i=0;i<n;i++){ for(int j=0;j<n-1;j++){ if(r[j]>r[j+1]){ swap(x[j],x[j+1]); swap(y[j],y[j+1]); swap(r[j],r[j+1]); } } } for(int i=0;i<n;i++){ x[i+n]=x[i];y[i+n]=y[i];r[i+n]=r[i]; } long long ret=999999999999999999LL; for(int L=0;L<=n;L++){ for(int R=0;L+R<=n;R++){ for(int U=0;L+R+U<=n;U++){ int D=n-L-R-U; long long dx=s-d*(R-L); long long dy=t-d*(U-D); if(dx<-d*(U+D)||dx>d*(U+D))continue; if(dy<-d*(R+L)||dy>d*(R+L))continue; for(int i=0;i<n;i++){ // printf("%d %d %d %d %d: ",D,R,U,L,i); int di=i; int ri=di+D; int ui=ri+R; int li=ui+U; long long xsum=0; long long ysum=0; long long cost=0; for(int j=0;j<D;j++){ if(r[di+j]/(2*d)==0)xsum+=x[di+j]; else{ xsum-=d; cost+=8*d-r[di+j]; } } for(int j=0;j<U;j++){ if(r[ui+j]/(2*d)==2)xsum+=x[ui+j]; else{ xsum+=d; cost+=8*d-(r[ui+j]+4*d)%(8*d); } } // printf("%lld %lld\n",xsum,dx); // printf("%lld ",cost); long long D1=cost; if(xsum>dx){ long long rem=xsum-dx; long long can=0; long long rev=0; long long val=999999999999999999LL; int ru=0; for(int j=0;j<U;j++){ long long za; if(4*d<=r[ui+j]&&r[ui+j]<6*d)za=x[ui+j]; else za=d; can+=za+d; }//if(can<rem)continue;cost+=rem; if(rem){ if(rem<=can)val=min(val,rem); for(int j=n-1;j>=0;j--){ if((di<=j&&j<di+D)||(di<=j+n&&j+n<di+D)){ if(0<r[j]&&r[j]<2*d){ rev+=r[j]; ru++; if(rem<=can+rev){ val=min(val,8*d*ru-min(rev,rem)+max(0LL,rem-rev)); } } } } } cost+=val; }else if(xsum<dx){ long long rem=dx-xsum; long long can=0;int ru=0; long long rev=0; long long val=999999999999999999LL; for(int j=0;j<D;j++){ long long za; if(0<=r[di+j]&&r[di+j]<2*d)za=x[di+j]; else za=-d; can+=d-za; }//if(can<rem)continue;cost+=rem; if(rem){ if(rem<=can)val=min(val,rem); for(int j=n-1;j>=0;j--){ if((ui<=j&&j<ui+U)||(ui<=j+n&&j+n<ui+U)){ if(4*d<r[j]&&r[j]<6*d){ rev+=r[j]-4*d; ru++; if(rem<=can+rev){ val=min(val,8*d*ru-min(rev,rem)+max(0LL,rem-rev)); } } } } } cost+=val; } // printf("%lld ",cost); long long D2=cost; for(int j=0;j<R;j++){ if(r[ri+j]/(2*d)==1)ysum+=y[ri+j]; else{ ysum-=d; cost+=8*d-(r[ri+j]+6*d)%(8*d); } } for(int j=0;j<L;j++){ if(r[li+j]/(2*d)==3)ysum+=y[li+j]; else{ ysum+=d; cost+=8*d-(r[li+j]+2*d)%(8*d); } } // printf("%lld ",cost); long long D3=cost; if(ysum>dy){ long long rem=ysum-dy; long long can=0;int ru=0; long long rev=0; long long val=999999999999999999LL; for(int j=0;j<L;j++){ long long za; if(6*d<=r[li+j]&&r[li+j]<8*d)za=y[li+j]; else za=d; can+=za+d; }//if(can<rem)continue;cost+=rem; if(rem){ if(rem<=can)val=min(val,rem); for(int j=n-1;j>=0;j--){ if((ri<=j&&j<ri+R)||(ri<=j+n&&j+n<ri+R)){ if(2*d<r[j]&&r[j]<4*d){ rev+=r[j]-2*d; ru++; if(rem<=can+rev){ val=min(val,8*d*ru-min(rev,rem)+max(0LL,rem-rev)); } } } } } cost+=val; }else if(ysum<dy){ long long rem=dy-ysum; long long can=0;int ru=0; long long rev=0; long long val=999999999999999999LL; for(int j=0;j<R;j++){ long long za; if(2*d<=r[ri+j]&&r[ri+j]<4*d)za=y[ri+j]; else za=-d; can+=d-za; }//if(can<rem)continue;cost+=rem; if(rem){ if(rem<=can)val=min(val,rem); for(int j=n-1;j>=0;j--){ if((li<=j&&j<li+L)||(li<=j+n&&j+n<li+L)){ if(6*d<r[j]&&r[j]<8*d){ rev+=r[j]-6*d; ru++; if(rem<=can+rev){ val=min(val,8*d*ru-min(rev,rem)+max(0LL,rem-rev)); } } } } } cost+=val; } // if(-3000<xsum-dx&&xsum-dx<3000)printf("%d %d %d %d %d: %lld %lld %lld %lld %lld %lld %lld %lld\n",D,R,U,L,i,xsum,dx,ysum,dy, D1,D2,D3,cost); ret=min(ret,cost); } } } } printf("%lld\n",ret+n); }