Codeforces #577 Div2 D. Treasure Hunting

似たようなネタを考えたことがあった。
https://codeforces.com/contest/1201/problem/D

問題

グリッド上プレイヤーは左下マスにいる。
グリッド上いくつかのマスにお宝がある。また、いくつかの列は安全である。
プレイヤーは時間1で左右に1マス移動でき、安全な列においては、上に1マス移動できる。
全お宝マスを通過する最小時間を求めよ。

解法

下には移動できないので、下の行から順にお宝を回収するしかない。
その際の選択肢は以下のとおりである。

• 行内の一番右/左のお宝まで行き、（残っていたら）反転して左/右のお宝に行き、そこから最寄の左or右の安全な列に移動して上の行に移る

結局上に移動する際に使う列の選択肢は多くないので、各列で上に移動する際の最小コストを求めていけばよい。

int H,W,K,Q;
vector<int> X[202020];
set<int> Y;
vector<int> C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K>>Q;
	int may=0;
	Y.insert(0);
	FOR(i,K) {
		cin>>y>>x;
		X[y-1].push_back(x-1);
		may=max(may,y-1);
		Y.insert(y-1);
	}
	FOR(i,Q) {
		cin>>x;
		C.push_back(x-1);
	}
	sort(ALL(C));
	
	map<int,ll> V;
	V[0]=0;
	
	FORR(y,Y) {
		if(y==0 && X[0].empty()) {
			V.clear();
			V[C[0]]=C[0];
			continue;
		}
		
		sort(ALL(X[y]));
		int L=X[y][0];
		int R=X[y].back();
		
		
		if(y==*Y.rbegin()) {
			ll mi=1LL<<60;
			FORR(v,V) {
				ll ret=v.second+min(abs(L-v.first),abs(R-v.first))+abs(R-L);
				mi=min(mi,ret);
			}
			cout<<mi+may<<endl;
			return;
		}
		
		map<int,ll> W;
		FORR(v,V) {
			// left
			ll ret=v.second+abs(R-v.first)+abs(L-R);
			x=lower_bound(ALL(C),L)-C.begin();
			
			if(x<Q) {
				if(W.count(C[x])==0) W[C[x]]=1LL<<60;
				W[C[x]]=min(W[C[x]],ret+abs(C[x]-L));
			}
			if(x) {
				x--;
				if(W.count(C[x])==0) W[C[x]]=1LL<<60;
				W[C[x]]=min(W[C[x]],ret+abs(C[x]-L));
			}
			
			// right
			ret=v.second+abs(L-v.first)+abs(L-R);
			x=lower_bound(ALL(C),R)-C.begin();
			if(x<Q) {
				if(W.count(C[x])==0) W[C[x]]=1LL<<60;
				W[C[x]]=min(W[C[x]],ret+abs(C[x]-R));
			}
			if(x) {
				x--;
				if(W.count(C[x])==0) W[C[x]]=1LL<<60;
				W[C[x]]=min(W[C[x]],ret+abs(C[x]-R));
			}
			
		}
		swap(V,W);
		
		
	}
	
	
	
}

まとめ

自分はマンションで郵便物を配達する設定で同じようなの考えてた。