kmjp's blog

競技プログラミング参加記です

TopCoder SRM 830 : Div1 Easy Div2 Hard Jetpack

雑な速解きで前回のロス分を挽回した。
https://community.topcoder.com/stat?c=problem_statement&pm=17599&rd=19227

問題

H*Wの大きさのグリッド上で、スタートとゴールの点が与えられる。
プレイヤーは、スタートの点からゴールの点に移動したい。
プレイヤーは空を飛ぶ装置を持っているが、バッテリーが空である。

以下の条件のもと、移動にかかる最小時間を求めよ。

  • 障害物のあるセルは通行不可
  • 隣接セルへは、時間1をかけ移動可能
  • 穴の開いたセルは、バッテリーの電力量を1消費して1マス通過可能
  • バッテリーチャージャーのあるセルでは、時間Tを掛け、バッテリーの電力量を1増やすことができる。バッテリーはいくらでも電力量を増やすことが可能。

解法

状態として現在位置とバッテリーの電力量を持てば、状態数がO((HW)^2)程度なので、そのままダイクストラ法で解ける。
ただ、もっと状態を削減することができる。
一端バッテリーチャージャーのあるマスを通過したら、以降は穴のあるマスを通る際に時間Tを余分にかければ通過可能、と考えれば、電力量を覚える必要がなく、状態数をO(HW)に落とすことができる。

ll dp[55][55][2];

class Jetpack {
	public:
	int travel(vector <string> S, int T) {
		int H=S.size();
		int W=S[0].size();
		int x,y,i;
		FOR(y,H) cout<<S[y].size()<<endl;
		FOR(y,H) FOR(x,W) FOR(i,2) dp[y][x][i]=1LL<<60;
		int sx,sy,gx,gy;
		priority_queue<pair<ll,int>> Q;
		FOR(y,H) FOR(x,W) {
			if(S[y][x]=='A') {
				sx=x,sy=y;
				S[y][x]='.';
				dp[y][x][0]=0;
				Q.push({0,y*50+x});
			}
			if(S[y][x]=='B') {
				gx=x,gy=y;
				S[y][x]='.';
			}
		}
		while(Q.size()) {
			ll co=-Q.top().first;
			int cy=Q.top().second/50%50;
			int cx=Q.top().second%50;
			int num=Q.top().second/2500;
			Q.pop();
			if(dp[cy][cx][num]!=co) continue;
			if(cy==gy&&cx==gx) return co;
			
			if(S[cy][cx]=='C') {
				if(dp[cy][cx][1]>co) {
					dp[cy][cx][1]=co;
					Q.push({-dp[cy][cx][1],(1)*2500+cy*50+cx});
				}
			}
			int d[4]={0,1,0,-1};
			FOR(i,4) {
				int ty=cy+d[i];
				int tx=cx+d[i^1];
				if(ty<0||ty>=H||tx<0||tx>=W) continue;
				if(S[ty][tx]=='#') continue;
				if(S[ty][tx]=='_'&&num==0) continue;
				if(dp[ty][tx][num]>co+1+(S[ty][tx]=='_')*T) {
					dp[ty][tx][num]=co+1+(S[ty][tx]=='_')*T;
					Q.push({-dp[ty][tx][num],num*2500+ty*50+tx});
				}
			}
			
		}
		
		return -1;
		
	}
}

まとめ

本番雑にO((HW)^2)の状態数のコードを書いてしまったが、通ってよかった。