AtCoder ABC #177 : F - I hate Shortest Path Problem

本番中焦ってやると実装がこんがらがりそうな問題。
https://atcoder.jp/contests/abc177/tasks/abc177_f

問題

(H+1)*Wの2次元グリッドがある。
最上段の任意のセルから、右または下の隣接セルをたどって移動することを考える。
この時、入力としてk行目と(k+1)行目の間は、A[k]列目～B[k]列目では下に移動できないという条件が与えられる。
2～(H+1)行目に至る最小移動回数をそれぞれ求めよ。

解法

行が決まれば下への移動回数は確定するので、あとは右への移動回数の最小値を求めよう。
各列について、その列に到達可能な最大の最上段の列番号を覚えておき、行毎に更新していくことを考える。
途中下方向に移動できない列は、左側にある移動可能な列のうち最も右の列の保持する列番号をコピーする、という手続きを考える。

setにこの覚えた列番号が変化する場所を格納しておき、その場所における右方向の移動回数をそれぞれmultisetで管理しよう。
multisetを使うことで右方向の移動回数の最小値を高速に取得できる。
列毎にsetやmultisetの内容は変化するが、数は維持するか減少する方向にしか至らないので均しで操作回数はO(H+W)で済む。

int H,W;
multiset<int> M;
set<pair<int,int>> S;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(x,W) {
		S.insert({x,x});
		M.insert(0);
	}
	S.insert({-1,-2000000});
	M.insert(20202020);
	S.insert({W,W});
	
	FOR(y,H) {
		int A,B;
		cin>>A>>B;
		A--,B--;
		while(1) {
			auto it=S.lower_bound({A,0});
			if(it->first>B) break;
			if(next(it)->first<=B+1) {
				M.erase(M.find(it->first-it->second));
				S.erase(it);
			}
			else {
				x=it->second;
				M.erase(M.find(it->first-it->second));
				S.erase(it);
				S.insert({B+1,x});
				M.insert({B+1-x});
			}
		}
		x=*M.begin()+y+1;
		if(x>=H+W) x=-1;
		cout<<x<<endl;
	}
}

まとめ

"I hate Shortest Path Problem"というタイトルなのに結局Shortest Pathを求めさせられるんだな。