yukicoder : No.2096 Rage With Our Friends

問題名になんか元ネタあるのかな。
https://yukicoder.me/problems/no/2096

問題

2次元グリッド上で、位置(SX,SY)にいるプレイヤーを(GX,GY)に移動させたい。
各マスは足場があるかないかのいずれかである。

プレイヤーはパラメータとしてエネルギーEを持つ。初期値は0とする。
プレイヤーは位置(X,Y)にいるとき、以下の手順を取れる

• 通常ジャンプ：X'≦X+1+floor(E/2)であるX'に対し、(X',Y+1)または(X',Y-1)のうち足場のあるマスに移動する。その後E=max(0,X-X')になる。
• ブーストジャンプ：X'≦X+1+EであるX'に対し、(X',Y+1)または(X',Y-1)のうち足場のあるマスに移動する。その後E=max(0,X-X')になる。

(GX,GY)に移動するブーストジャンプの最小回数を求めよ。

解法

各位置に到達するブーストジャンプ回数の最小値を、01BFSで求めよう。
その際、プレイヤーの状態としてエネルギーも考えると、状態数が多くなりTLE/MLEとなる。
そこで、X座標が下がる移動とその直後の通常ジャンプまたはブーストジャンプをまとめて行うことにする。
その際は、できるだけX座標が大きくなるように移動するのが最適なので、移動先のY座標を定めるとX座標も最適な位置に一意に定まる。

int H,W,SX,GX,SY,GY;
string S[2010];
int U[2010][2010];
int D[2010][2010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>SY>>SX>>GY>>GX;
	SY--,GY--;
	SX--,GX--;
	FOR(y,H) cin>>S[y];
	S[H]=string(W,'#');
	H++;
	FOR(x,W) {
		FOR(y,H) {
			D[y][x]=1<<30;
			if(y) U[y][x]=U[y-1][x];
			else U[y][x]=-1;
			if(S[y][x]=='.') U[y][x]=y;
		}
	}
	deque<int> Q;
	D[SY][SX]=0;
	Q.push_back(SY*2000+SX);
	while(Q.size()) {
		int cy=Q.front()/2000;
		int cx=Q.front()%2000;
		Q.pop_front();
		int co=D[cy][cx];
		if(cy==GY&&cx==GX) {
			cout<<co<<endl;
			return;
		}
		
		for(int tx=cx-1;tx<=cx+1;tx+=2) if(tx>=0&&tx<W) {
			y=U[cy+1][tx];
			if(y<0) continue;
			if(chmin(D[y][tx],co)) Q.push_front(y*2000+tx);
			if(y<cy) {
				int hy=cy+1;
				int sy=y+(cy-y)/2+1;
				for(int tx2=tx-1;tx2<=tx+1;tx2+=2) if(tx2>=0&&tx2<W) {
					int ny=U[hy][tx2];
					if(ny>=0&&chmin(D[ny][tx2],co+1)) Q.push_back(ny*2000+tx2);
					ny=U[sy][tx2];
					if(ny>=0&&chmin(D[ny][tx2],co)) Q.push_front(ny*2000+tx2);
				}
			}
		}
	}
	cout<<-1<<endl;
}

まとめ

Friendsにどこに行ったのだろう。