Saiko~ No Contesuto #03 : ぐるぐるツアー

しょうもないWAを繰り返した…。
https://www.hackerrank.com/contests/camypapercon03/challenges/guruguru-tour

問題

プレイヤーは２次元座標の原点におり、初期状態で上下左右任意の向きを向ける。
プレイヤーは以下のいずれかの行動を繰り返すことができる。

• 向いている方向に１進む
• 向いている方向に１進んだ後、向きを時計回りに90度変える。

N個の点(座標は(X[i],Y[i]))をすべて(任意の順番で)訪れたい。
必要な最小行動回数を求めよ。

解法

dp[訪問済みののbitmask][最後に到達した点][最後に到達した点の向き] := その状態に至る最小コスト
として愚直にbitdpをしていけば良い。

ある座標にある向きでいるとき、次に別のある座標に狙った向きでいるための行動回数は面倒だけど愚直に場合分けしよう。
もっと簡単な方法あるのかしら？

int N;
ll X[15],Y[15];
ll dp[1<<13][15][4];
ll dist[15][15][4][4];

ll di(ll DX,ll DY,int s,int t) {
	if(s>0) return di(-DY,DX,s-1,(t+3)%4);
	vector<int> V;
	
	if(DY>=0 && DX<=0) V={4,6,8,4};
	else if(DY<0 && DX<=0) V={4,6,2,2};
	else if(DY==0 && DX>0) V={0,0,6,4};
	else if(DX>0 && DY>0) V={4,4,6,4};
	else if(DX>0 && DY<0) V={4,0,0,2};
	else assert(0);
	
	return abs(DX)+abs(DY)+V[t];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i+1]>>Y[i+1];
	N++;
	
	FOR(i,N) FOR(j,N) if(i!=j) {
		FOR(x,4) FOR(y,4) dist[i][j][x][y] = di(X[j]-X[i],Y[j]-Y[i],x,y);
	}
	FOR(i,4) dp[1][0][i]=0;
	for(int mask=2;mask<1<<N;mask++) {
		FOR(x,4) FOR(i,N) if(mask&(1<<i)) {
			dp[mask][i][x]=1LL<<40;
			FOR(j,N) if((mask&(1<<j)) && (i!=j)) {
				FOR(y,4) dp[mask][i][x] = min(dp[mask][i][x],dp[mask^(1<<i)][j][y] + dist[j][i][y][x]);
			}
		}
	}
	
	ll mi=1LL<<40;
	FOR(i,4) FOR(j,N) mi=min(mi,dp[(1<<N)-1][j][i]);
	cout<<mi<<endl;
	
}

まとめ

２頂点の移動コストが2^31を超えてintからあふれるというしょうもないミスを繰り返した。