AtCoder ARC #122 (東京海上日動 プログラミングコンテスト2021) : F - Domination

このグラフの作り替えテクは覚えておきたい。
https://atcoder.jp/contests/arc122/tasks/arc122_f

問題

2次元座標上に、赤い点N個と青い点M個が与えられる。
青い点を動かし、各赤い点に対し、自身の右上にK個以上の青点が来るようにしたい。
青い点を1つ軸に沿って1動かすのにかかるコストを1としたとき、条件を満たす最小総コストを求めよ。

解法

まず、赤い点同士のうち、自身の右上に他の赤点があるようなものは考える必要がないので削除しておく。
そうすると、考えるべき赤点は、左上から右下に並んだ形になる。

この時、青点を適当に動かすと、1つの青点は上記赤点列の区間をカバーすることになる。
あとは、各赤点がK個以上の青点でカバーされるようにすればよい。

Y軸上の格子点に対応する点と、X軸上の格子点に対応する点からなるグラフを考える。
Y軸上を正方向・負方向に移動するコストを0・1、X軸上を正方向・負方向に移動するコストを1・0とする。
また、青点については、対応する座標に応じたY軸上の点からX軸上の点にコスト0の辺を張る。

まず、K=1の場合を考える。
この時、i番目の赤点のY座標に対応する点から、j番目の赤点のX座標に対応する点への最小コストを求めると、これはこの点をカバーする青点の動かし方の最小コストとなる。
そこで、i番目の赤点のX座標に対応する点から、(i+1)番目の赤点のY座標に対応する点へコスト0の辺を張ろう。
そうすると、最初の赤点のY座標に対応する点から、最後の赤点のX座標に対応する点へのコストを求めれば、これはいくつかの青点を動かすことで、全赤点がカバーされることになる。

Kが1以上の場合、青点に対応する辺の容量を1、それ以外の辺の容量を無限大として、フローKに対する最小コストを求めればよい。

template<int NV,class V> class MinCostFlow {
public:
	struct edge { int to; V capacity; V cost; int reve;};
	vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV]; V pot[NV];
	void add_edge(int x,int y, V cap, V cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	V mincost(int from, int to, ll flow) {
		V res=0; int i,v;
		ZERO(prev_v); ZERO(prev_e); fill(pot, pot+NV, 0);
		while(flow>0) {
			fill(dist, dist+NV, numeric_limits<V>::max()/2);
			dist[from]=0;
			priority_queue<pair<V,int> > Q;
			Q.push(make_pair(0,from));
			while(Q.size()) {
				V d=-Q.top().first;
				int cur=Q.top().second;
				Q.pop();
				if(dist[cur]!=d) continue;
				if(d==numeric_limits<V>::max()/2) break;
				FOR(i,E[cur].size()) {
					edge &e=E[cur][i];
					if(e.capacity>0 && dist[e.to]>d+e.cost+pot[cur]-pot[e.to]) {
						dist[e.to]=d+e.cost+pot[cur]-pot[e.to];
						prev_v[e.to]=cur;
						prev_e[e.to]=i;
						Q.push(make_pair(-dist[e.to],e.to));
					}
				}
			}
			
			if(dist[to]==numeric_limits<V>::max()/2) return -1;
			V lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			FOR(i,NV) pot[i]+=dist[i];
			flow -= lc;
			res += lc*pot[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};
MinCostFlow<410101,ll> mcf;

int N,M,K;
int RX[101010],RY[101010];
int BX[101010],BY[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	vector<pair<int,int>> R,R2;
	vector<int> Xs,Ys;
	Xs.push_back(0);
	Ys.push_back(0);
	FOR(i,N) {
		cin>>x>>y;
		R2.push_back({x,y});
		Xs.push_back(x);
		Ys.push_back(y);
	}
	sort(ALL(R2));
	FORR2(x,y,R2) {
		while(R.size()&&R.back().second<=y) R.pop_back();
		R.push_back({x,y});
	}
	FOR(i,M) {
		cin>>BX[i]>>BY[i];
		Xs.push_back(BX[i]);
		Ys.push_back(BY[i]);
	}
	sort(ALL(Xs));
	sort(ALL(Ys));
	Xs.erase(unique(ALL(Xs)),Xs.end());
	Ys.erase(unique(ALL(Ys)),Ys.end());
	
	x=Ys.size()-1;
	FOR(i,x) {
		mcf.add_edge(i,i+1,1<<20,Ys[x-i]-Ys[x-(i+1)]);
		mcf.add_edge(i+1,i,1<<20,0);
	}
	FOR(i,Xs.size()-1) {
		mcf.add_edge(x+1+i,x+1+i+1,1<<20,Xs[i+1]-Xs[i]);
		mcf.add_edge(x+1+i+1,x+1+i,1<<20,0);
	}
	
	N=R.size();
	FOR(i,N) {
		RX[i]=lower_bound(ALL(Xs),R[i].first)-Xs.begin();
		RY[i]=lower_bound(ALL(Ys),R[i].second)-Ys.begin();
		if(i) {
			mcf.add_edge(x+1+RX[i-1],x-RY[i],1<<20,0);
		}
	}
	FOR(i,M) {
		BX[i]=lower_bound(ALL(Xs),BX[i])-Xs.begin();
		BY[i]=lower_bound(ALL(Ys),BY[i])-Ys.begin();
		mcf.add_edge(x-BY[i],x+1+BX[i],1,0);
	}
	
	ll ret=mcf.mincost(x-RY[0],x+1+RX[N-1],K);
	cout<<ret<<endl;

}

まとめ

DPじゃ解けないしフローかな…とは思ったけど、このフローは思いつけなかった。