CPSCO2019 Session2 : F - Treasure Collector

勉強になりました。
https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_f

問題

N*Nのグリッドがある。
初期状態で、N箇所のセルにロボットがいる。
これらのロボットは、同じ列・同じ行には2体以上いない。

ここで、全マスにコインが1個ずつ置かれており、ロボットがそれらを回収することを考える。
ロボットは上下左右とコイン枚数をを指定すると、1回でいずれかの向きに対し、手前から指定した枚数分のコインを回収して元の位置に戻る。
この際、各ロボットiは1回の指定の上限A[i]が与えられる。
また、いったんロボットが通ったマスは、他のロボットは踏み入れることができないとする。

全コインを回収するのに必要なロボットの操作回数の最小値を求めよ。

解法

初期状態にロボットがいない各セルは、同じ列か同じ行のいずれかのロボットによりコインが回収されなければならない。
そこで、縦方向に回収されるか横方向に回収されるかどちらが良いかを考える。

複数の変数が、2つの選択肢のうちどちらを選択するとコストの総和が最小になるか、という問題は、いわゆる燃やす埋める問題として最大フローに変換できるケースがあることが知られている。
ただ自分は燃やす埋めるだと辺の張り方が直感的でないので、とこはるさんのProjectSelectionProblemの説明を参考に解いた。

『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ

このブログの記述によると、以下のパターンの問題を最大フローに置き換えられる。
『N 個の要素がある。最初どの頂点も集合 B に属しているが、これを集合 A に移すことで利益を最大化したい。要素 i が A に属する時には利得 p_i を得るという情報が与えられる。さらに 3 つ組の列 (xj, yj, zj) が与えられ、これは xj が A に属し、かつ yj が B に属していた時に zj(≥ 0) だけ損失をすることを意味する。得られる利得の最大値を答えよ。』

これを今回の問題に置き換えると、以下のようにできる。
『N*N個のセルがあり、最初どのセルもロボットが横方向に動いて回収されるものとする。
これを一部縦方向に動いて回収させることで利益を最大化したい。
ロボットが各セルに到達するときには、操作回数を何回要するという情報が与えられる。
さらにあるセルのコインが縦ないし横方向に回収されるとき、その隣接セルは同じ方向に回収されなければならない（別の方向に回収すると無限大の損失が得られる）とする。
このときコストを最小化せよ。』

各セル縦横方向に回収する場合のコストの減少分を利益としてグラフを作り、最大フローを求めれば、横方向だけの回収を用いるときに対するコストの減少分がわかる。
ロボットが踏み入ることができない、の条件は、上でも少し言い換えているが、例えば
「あるセルのコインが横方向に回収されるとき、右からロボが来るならば、その右マスは縦に回収されてはならない」
というように考えることができる。

int N;
int X[90];
int A[90];

template<class V> class MaxFlow_dinic {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 11000;
	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();
			ITR(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;
		}
	}
};
MaxFlow_dinic<int> mf;
int C[80][80],SA,SB;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) cin>>X[y], X[y]--;
	FOR(y,N) cin>>A[y];
	
	FOR(y,N) {
		// LR
		for(x=0;x<N;x++) if(x!=X[y]&&(abs(X[y]-x)-1)%A[y]==0) C[y][x]--,SA++;
		for(x=0;x<N;x++) if(x!=y&&(abs(y-x)-1)%A[y]==0) C[x][X[y]]++,SB++;
		for(x=0;x<X[y]-1;x++) mf.add_edge(y*N+x,y*N+x+1,1<<20);
		for(x=X[y]+2;x<N;x++) mf.add_edge(y*N+x,y*N+x-1,1<<20);
		for(x=0;x<y-1;x++) mf.add_edge((x+1)*N+X[y],(x)*N+X[y],1<<20);
		for(x=y+2;x<N;x++) mf.add_edge((x-1)*N+X[y],(x)*N+X[y],1<<20);
	}
	int sp=0;
	FOR(y,N) FOR(x,N) {
		if(C[y][x]==1) mf.add_edge(N*N,y*N+x,1);
		if(C[y][x]==-1) mf.add_edge(y*N+x,N*N+1,1);
		sp+=max(0,C[y][x]);
	}
	
	cout<<SB-(sp-mf.maxflow(N*N,N*N+1))<<endl;
	
}

まとめ

今後活用させていただきます。