AtCoder ABC #170 : F - Pond Skater

意外にシンプルに解けるのね。
https://atcoder.jp/contests/abc170/tasks/abc170_f

問題

グリッド上で、一部のセルは移動不可である。
あるセルからあるセルに移動したい。
その際、コスト1で上下左右1方向に最大Kマスまで(移動不可のセルを通らない範囲で)移動できる。
目的のセルまでの最小移動コストを求めよ。

解法

コストを1/Kの何倍か、で考える。
各セルにおいて、直前の移動の向きを含めて最小コストを持つことにする。
通常の移動ではコスト1で済むが、向きを変える場合はコストがKの倍数に繰り上げされる、と考えるようにすると、後は単なるダイクストラ法に落とすことができる。

int N,Q;
int A[202020],B[202020];
multiset<int> K[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		K[B[i]].insert(-A[i]);
	}
	
	multiset<int> cand;
	for(i=1;i<=200000;i++) {
		if(K[i].size()) cand.insert(-*K[i].begin());
	}
	
	while(Q--) {
		int C,D;
		cin>>C>>D;
		C--;
		cand.erase(cand.find(-*K[B[C]].begin()));
		K[B[C]].erase(K[B[C]].find(-A[C]));
		if(K[B[C]].size()) cand.insert(-*K[B[C]].begin());
		B[C]=D;
		if(K[D].size()) cand.erase(cand.find(-*K[D].begin()));
		K[D].insert(-A[C]);
		cand.insert(-*K[D].begin());
		cout<<*cand.begin()<<endl;
	}
	
	
}

まとめ

今回本番不参加だったけど、本番だと地味に手間取りそう。