kmjp's blog

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

TopCoderOpen 2019 Round3B : Easy TwoLadders

これはほぼ同じ問題を考えたことがあったので余裕だった。
https://community.topcoder.com/stat?c=problem_statement&pm=15623&rd=17617

問題

ある建物にいくつかのコインが配置されており、それを回収したい。
この建物は横方向は任意に移動できるが、縦方向は2か所に設置された垂直な梯子を使ってしか移動できない。
また、この梯子は上にしか移動できない。

全コインを回収する最短移動距離を求めよ。

解法

コインの置いてある各縦座標について、コインを回収して両梯子に戻る最短経路を順次計算していこう。
コインを回収するには、その縦座標にある最も左と最も右のコインを回収すればよいので、移動経路は以下のいずれか。

  • 左梯子→左端コイン→右端コイン→左梯子
  • 左梯子→左端コイン→右端コイン→右梯子
  • 右梯子→左端コイン→右端コイン→左梯子
  • 右梯子→左端コイン→右端コイン→右梯子
  • 左梯子→右端コイン→左端コイン→左梯子
  • 左梯子→右端コイン→左端コイン→右梯子
  • 右梯子→右端コイン→左端コイン→左梯子
  • 右梯子→右端コイン→左端コイン→右梯子

なお、縦座標0のみ開始位置が梯子ではないことと、もっとも高い位置ではコインを回収して終了なので、梯子に戻らなくてよい点に注意。

class TwoLadders {
	public:
	long long minSteps(int sx, int lx1, int lx2, vector <int> X, vector <int> Y) {
		map<ll,pair<ll,ll>> M;
		int i;
		FOR(i,X.size()) {
			if(M.count(Y[i])==0) {
				M[Y[i]]={(ll)X[i],(ll)X[i]};
			}
			else {
				M[Y[i]].first=min(M[Y[i]].first,(ll)X[i]);
				M[Y[i]].second=max(M[Y[i]].second,(ll)X[i]);
			}
		}
		
		if(M.size()==1 && M.begin()->first==0) {
			ll x1=M[0].first,x2=M[0].second;
			return min(abs(sx-x1)+abs(x2-x1),abs(sx-x2)+abs(x2-x1));
		}
		
		
		ll L,R;
		if(M.count(0)) {
			ll x1=M[0].first,x2=M[0].second;
			L=min(abs(sx-x1)+abs(x2-x1)+abs(x2-lx1),abs(sx-x2)+abs(x2-x1)+abs(x1-lx1));
			R=min(abs(sx-x1)+abs(x2-x1)+abs(x2-lx2),abs(sx-x2)+abs(x2-x1)+abs(x1-lx2));
		}
		else {
			L=abs(sx-lx1);
			R=abs(sx-lx2);
		}
		FORR(m,M) {
			if(m.first==0) continue;
			if(m.first==M.rbegin()->first) continue;
			ll x1=m.second.first,x2=m.second.second;
			ll PL=L,PR=R;
			L=min({PL+abs(x1-lx1)+abs(x2-x1)+abs(lx1-x2),PL+abs(x2-lx1)+abs(x2-x1)+abs(lx1-x1),PR+abs(x1-lx2)+abs(x2-x1)+abs(lx1-x2),PR+abs(x2-lx2)+abs(x2-x1)+abs(lx1-x1)});
			R=min({PL+abs(x1-lx1)+abs(x2-x1)+abs(lx2-x2),PL+abs(x2-lx1)+abs(x2-x1)+abs(lx2-x1),PR+abs(x1-lx2)+abs(x2-x1)+abs(lx2-x2),PR+abs(x2-lx2)+abs(x2-x1)+abs(lx2-x1)});
		}
		ll x1=M.rbegin()->second.first,x2=M.rbegin()->second.second;
		ll ret=min({L+abs(x1-lx1)+abs(x2-x1),L+abs(x2-lx1)+abs(x2-x1),R+abs(x1-lx2)+abs(x2-x1),R+abs(x2-lx2)+abs(x2-x1)});
		return ret+M.rbegin()->first;
		
		
	}
}

まとめ

コーナーケース対策が面倒だな。