この回は不参加だった。
http://codeforces.com/contest/1421/problem/D
問題
ヘックス状のグリッドがある。
6方向それぞれ1マス移動するコストと、目的地となるマス目の座標が与えられる。
原点から目的地に移動する最小コストを求めよ。
解法
ヘックス状のグリッドであっても、結局2つの座標軸で各セルが表現できる点で、通常のスクエア状のグリッドは変わらない。
そこで、まずスクエア状のグリッドとみなし、8方向の最小移動コストを求めよう。
あとは、極力斜め移動を使って目的地に移動しよう。
その際は、X座標が合うところまで斜め移動して縦移動するか、Y座標が合うところまで斜め移動して横移動するか、両方試そう。
int T; ll X,Y; ll C[6]; ll pat[3][3]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>X>>Y; FOR(i,6) cin>>C[i]; FOR(x,3) FOR(y,3) pat[x][y]=1LL<<60; pat[2][2]=C[0]; pat[1][2]=C[1]; pat[0][1]=C[2]; pat[0][0]=C[3]; pat[1][0]=C[4]; pat[2][1]=C[5]; int x2,y2; FOR(i,8) { for(x=-1;x<=1;x++) for(y=-1;y<=1;y++) { for(x2=-1;x2<=1;x2++) for(y2=-1;y2<=1;y2++) { int tx=x+x2; int ty=y+y2; if(abs(tx)>=2) continue; if(abs(ty)>=2) continue; pat[1+tx][1+ty]=min(pat[1+tx][1+ty],pat[1+x][1+y]+pat[1+x2][1+y2]); } } } if(X<0) { FOR(y,3) swap(pat[2][y],pat[0][y]); X=-X; } if(Y<0) { FOR(x,3) swap(pat[x][2],pat[x][0]); Y=-Y; } ll ret=X*pat[2][1]+Y*pat[1][2]; if(X<=Y) { // move X ret=min(ret,X*pat[2][2]+(Y-X)*pat[1][2]); // move Y ret=min(ret,Y*pat[2][2]+(Y-X)*pat[0][1]); } else { // move X ret=min(ret,X*pat[2][2]+(X-Y)*pat[1][0]); // move Y ret=min(ret,Y*pat[2][2]+(X-Y)*pat[2][1]); } cout<<ret<<endl; } }
まとめ
Div2Dにしては簡単。