tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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);
}