Google Code Jam 2022 Round 2 : C. Saving the Jelly

これは後半パートに気付くの難しいかも。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec/0000000000b158f8

問題

2次元座標上にN人の子供と(N+1)個の飴がある。
子供に1人1つずつ、以下のアルゴリズムで飴を取らせる。

• 飴を取る子供の順番は、任意に指定できる。
• 子供は自分が飴を取る番が来たら、最寄の飴を1つ取る。もし等距離で複数の飴がある場合、その中で取る飴を指定できる。

飴のうち、1つ子供に取らせたくないものがある。
可能であれば、その飴を子供に取らせないよう、飴を取る子供の順番と取る飴を指定せよ。

解法

まず子供がどの飴を取るべきかを考える。
各子供は、取らせたくない飴以下の距離にある飴は取れる可能性がある。
そこで、子供と飴の二部マッチングを求めよう。

次に、順番を考える。
ある時点で子供にマッチングしている飴が、子供から最寄りにあるなら問題なく子供はその飴を取ればよい。
ただし、一部の子供が、「先にあの飴を回収してくれないと、自分がマッチングした飴を回収できない」という関係が閉路となる可能性がある。

その場合、以下の手順でマッチングを変え閉路を解消することができる。

• 子供aが飴xとマッチしている場合、xの代わりにaの最寄の飴yを取る。
• その場合、飴yとマッチする子供bは、yではなく代わりにbの最寄の飴zを取る。
• その場合、飴zとマッチする子供cは…

int N;
ll CX[1010],CY[1010];
ll DX[1010],DY[1010];
ll D[1010][1010];

template<class V> class MaxFlow_dinic {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 2100;
	vector<edge> E[MV];
	int itr[MV],lev[MV];
	void add_edge(int x,int y,V cap,bool undir=false) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0});
	}
	void bfs(int cur) {
		MINUS(lev);
		queue<int> q;
		lev[cur]=0;
		q.push(cur);
		while(q.size()) {
			int v=q.front(); q.pop();
			FORR(e,E[v]) if(e.cap>0 && lev[e.to]<0) lev[e.to]=lev[v]+1, q.push(e.to);
		}
	}
	V dfs(int from,int to,V cf) {
		if(from==to) return cf;
		for(;itr[from]<E[from].size();itr[from]++) {
			edge* e=&E[from][itr[from]];
			if(e->cap>0 && lev[from]<lev[e->to]) {
				V f=dfs(e->to,to,min(cf,e->cap));
				if(f>0) {
					e->cap-=f;
					E[e->to][e->reve].cap += f;
					return f;
				}
			}
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			bfs(from);
			if(lev[to]<0) return fl;
			ZERO(itr);
			while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf;
		}
	}
};

int op[1010],rev[1010];
int sm[1010];
int didA[1010],didB[1010];
vector<pair<ll,int>> cand[1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	MaxFlow_dinic<int> mf;
	
	cin>>N;
	FOR(i,N) cin>>CX[i]>>CY[i];
	FOR(i,N+1) cin>>DX[i]>>DY[i];
	FOR(x,N) {
		mf.add_edge(2010,x,1);
		mf.add_edge(1001+x,2011,1);
		cand[x].clear();
		FOR(y,N+1) {
			D[x][y]=(CX[x]-DX[y])*(CX[x]-DX[y])+(CY[x]-DY[y])*(CY[x]-DY[y]);
			if(y) cand[x].push_back({-D[x][y],y});
		}
		sort(ALL(cand[x]));
		FOR(y,N+1) if(D[x][y]<=D[x][0]) mf.add_edge(x,1000+y,1);
	}
	
	x=mf.maxflow(2010,2011);
	if(x<N) {
		cout<<"Case #"<<_loop<<": IMPOSSIBLE"<<endl;
		return;
	}
	
	ZERO(sm);
	FOR(x,N) FORR(e,mf.E[x]) if(e.to<2001&&e.cap==0) {
		op[x]=e.to-1000;
		rev[op[x]]=x;
	}
	
	ZERO(didA);
	ZERO(didB);
	vector<pair<int,int>> V;
	while(1) {
		queue<int> Q;
		ZERO(sm);
		FOR(x,N) if(didA[x]==0) {
			FOR(y,N+1) if(didB[y]==0&&D[x][y]<D[x][op[x]]) sm[x]++;
			if(sm[x]==0) Q.push(x);
		}
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			V.push_back({x+1,op[x]+1});
			didA[x]=didB[op[x]]=1;
			FOR(y,N) if(D[y][op[y]]>D[y][op[x]]) {
				sm[y]--;
				if(sm[y]==0) Q.push(y);
			}
		}
		FOR(i,N) if(didA[i]==0) break;
		if(i==N) break;
		
		vector<int> S;
		int cur=i;
		FOR(j,N+5) {
			S.push_back(cur);
			while(1) {
				x=cand[cur].back().second;
				if(didB[x]==0) break;
				cand[cur].pop_back();
			}
			cur=rev[x];
		}
		for(i=S.size()-2;i>=0;i--) if(S[i]==S.back()) break;
		for(j=i+1;j<S.size();j++) {
			x=S[j];
			y=cand[S[j]].back().second;
			op[x]=y;
			rev[y]=x;
		}
	}
	cout<<"Case #"<<_loop<<": POSSIBLE"<<endl;
	FORR2(a,b,V) cout<<a<<" "<<b<<endl;
	
	
	//_P("Case #%d:\n",_loop);
}

まとめ

マッチング思いついた後も割としんどい。