kmjp's blog

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

AtCoder ARC #085 : E - MUL

開始時刻に間に合わず不参加でした。
https://beta.atcoder.jp/contests/arc085/tasks/arc085_c

問題

1~N番の番号が振られたN個の宝石があり、それぞれA[i]の整数が書かれている。
A[i]は負の場合もある。
この中の一部の宝石を壊すことにする。
ただしある宝石を壊した場合、その倍数の番号の宝石も壊さなければならない。

残された宝石に書かれた整数の和を最大化せよ。

解法

自分はいわゆる「燃やす埋める問題」の類題として解いたが、結果的に(一部で話題の?)Project Selectionの考え方に近い解法になっていたようだ。

壊す宝石間に関係がなく、任意に壊す宝石を選べる場合、A[i]が非負の宝石をすべて残し、負の宝石を壊すのが最適手である。
しかし実際には倍数の宝石を壊す制限により、もっと少ない和しか得られない可能性がある。
この減少量を最小化することを考えよう。これには最小カット=最大フローを用いる。

(N+2)頂点のグラフを考える。
source, sinkの他にN個の宝石に対応する頂点を持つ。
まず倍数の制限を除き、以下のように辺を張る。

  • A[i]が正の場合、sourceから宝石に対応する頂点にA[i]の容量の辺を張る
  • A[i]が負の場合、宝石に対応する頂点からsinkにA-[i]の容量の辺を張る

sourceから宝石に対応する点にフローが流れるということは、A[i]が正の宝石を壊すことで総和が減少することに相当し、宝石に対応する点からsinkにフローが流れるということは、A[i]が負の宝石を壊さないことで総和が減少することに相当する。
これだけなら、このグラフはsourceとsinkがつながらないので当然フローは0である。
しかし残念ながら倍数に関する制限により宝石に対応する頂点間に辺を張る結果、フローが流れてしまうことになる。
a番の宝石を壊すことを選ぶ場合、aの倍数であるb番の宝石も壊れなければいけない。
こればb番の宝石からa番の宝石の頂点に容量無限大の有向辺を張ることで表現できる。

これはどういうことか、シンプルにa=1,b=2の例を考える。
A[1]を負、A[2]を正とする。
今1番の宝石を単独で壊せられればいいのだが、問題文の条件より1番と2番はセットで壊さなければならない。
よって1番を壊すことによりセットで2番を壊す損失と、壊さないことで利益を失う損失を天秤に掛けることになる。
今回作成するグラフでは、以下のように辺が張られる。このグラフの最小カット=最大フローはmin(A[2],-A[1])なのは明らかだろう。

   A[2]     inf     -A[1]
s ----> (2) -----> (1) -----> t

実際はもっと点や辺の数が増えるが、結局はこれの延長で壊す場合と壊さない場合の損失の小さい方を求めていることになる。
よってA[i]の値が正であるものの総和から、上記手順で構築したグラフの最大フローを引いたものが答え。

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 10000;
	vector<edge> E[MV];
	int vis[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});
	}
	V dfs(int from,int to,V cf) {
		V tf;
		if(from==to) return cf;
		vis[from]=1;
		FORR(e,E[from]) if(vis[e.to]==0 && e.cap>0 && (tf = dfs(e.to,to,min(cf,e.cap)))>0) {
			e.cap -= tf;
			E[e.to][e.reve].cap += tf;
			return tf;
		}
		return 0;
	}
	V maxflow(int from, int to) {
		V fl=0,tf;
		while(1) {
			ZERO(vis);
			if((tf = dfs(from,to,numeric_limits<V>::max()))==0) return fl;
			fl+=tf;
		}
	}
};

MaxFlow_Ford<ll> mf;

int N;
int A[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll tot=0;
	for(i=1;i<=N;i++) {
		cin>>A[i];
		if(A[i]>=0) {
			tot+=A[i];
			mf.add_edge(0,i,A[i]);
			mf.add_edge(i,N+1,0);
		}
		else {
			mf.add_edge(0,i,0);
			mf.add_edge(i,N+1,-A[i]);
		}
		
		for(x=i*2;x<=N;x+=i) mf.add_edge(x,i,1LL<<40);
	}
	cout<<tot-mf.maxflow(0,N+1)<<endl;
}

まとめ

毎度自分は「燃やす埋める問題」のグラフの構築で迷うのだが、その結果Project Selectionという単語や概念を知らなかったのに、そちらの解法に近づいたことは興味深いことだ。