kmjp's blog

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

AtCoder ABC #394 (鹿島建設プログラミングコンテスト2025) : G - Dense Buildings

これはすんなり。
https://atcoder.jp/contests/abc394/tasks/abc394_g

問題

H*Wのグリッド状に建物が立っており、それぞれの階数が与えられる。
隣接マスにある建物は、(両者の上限以下の階であれば)同じ階同士で移動できる。

以下のクエリに順次答えよ。

  • 指定された2つの建物の位置と階について、互いに移動する際の階の上下移動回数の最小値。隣接マスへの建物の移動回数はカウントしない。

解法

2つの建物間同士で移動する際、移動経路中で最も低い階の建物に合わせいったん階段を下りる必要がある可能性がある。
そのため、極力高い建物を通るようにしたい。

そこで以下のようにする。
まず、クエリで指定された2つの建物に対し、クエリ番号を対応付けておく。
建物を高い順にソートし、順に移動可能フラグを付けよう。
その際、H*Wの無向グラフを考え、隣接する建物が互いに移動可能となった時点で両者の間に辺を張って連結成分とする。
もし途中でクエリで指定された2つの建物が同じ連結成分に含まれるようになった場合、その時点で2つの建物間で移動する際に通るべき最も低い階がわかるので、クエリの解が求められる。

上記作業では、連結成分内に含まれるクエリ番号を覚えておかないといけないが、そこはマージテクで行える。

int H,W;
int F[505][505];
int Q;
int Y1[202020],X1[202020];
int Y2[202020],X2[202020];
int S[202020],E[202020];
set<int> Qs[505*505];
int ret[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<505*505> uf;

void merge(int y1,int x1,int y2,int x2,int h) {
	if(F[y2][x2]<h) return;
	int a=uf[y1*W+x1];
	int b=uf[y2*W+x2];
	if(a==b) return;
	if(Qs[a].size()<Qs[b].size()) swap(a,b);
	FORR(v,Qs[b]) {
		if(Qs[a].count(v)) {
			Qs[a].erase(v);
			if(h<min(S[v],E[v])) {
				ret[v]=S[v]+E[v]-2*h;
			}
			else {
				ret[v]=abs(S[v]-E[v]);
			}
		}
		else {
			Qs[a].insert(v);
		}
	}
	Qs[b].clear();
	int k=uf(a,b);
	if(b==k) swap(Qs[a],Qs[b]);
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<pair<int,int>> ev;
	cin>>H>>W;
	FOR(y,H) FOR(x,W) {
		cin>>F[y][x];
		ev.push_back({F[y][x],y*W+x});
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>Y1[i]>>X1[i]>>S[i]>>Y2[i]>>X2[i]>>E[i];
		Y1[i]--,X1[i]--;
		Y2[i]--,X2[i]--;
		if(Y1[i]==Y2[i]&&X1[i]==X2[i]) {
			ret[i]=abs(S[i]-E[i]);
		}
		else {
			Qs[Y1[i]*W+X1[i]].insert(i);
			Qs[Y2[i]*W+X2[i]].insert(i);
		}
	}
	sort(ALL(ev));
	reverse(ALL(ev));
	FORR2(h,pos,ev) {
		int ty=pos/W;
		int tx=pos%W;
		
		if(ty) merge(ty,tx,ty-1,tx,h);
		if(ty+1<H) merge(ty,tx,ty+1,tx,h);
		if(tx) merge(ty,tx,ty,tx-1,h);
		if(tx+1<W) merge(ty,tx,ty,tx+1,h);
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

この回はなんかFの方が苦戦した。