AtCoder ARC #031 : D - 買い物上手

このタイプ苦手…。
http://arc031.contest.atcoder.jp/tasks/arc031_4

問題

このゲームでは、M個のアイテムのうち幾つかをそろえると経験値がもらえる。
経験値がもらえるアイテムの組み合わせはN個ある。
各アイテム集合A[i]に含まれるアイテムをすべて持っていると、経験値S[i]が手に入る。
各アイテムを購入するには、T[i]のお金がかかる。
なお、各アイテムは１個持っていれば、複数の集合に対し経験値が得られる。

(取得経験値/使用金額)を最大化せよ。

解法

部分点は、Nが20以下なので、2^N通りアイテムの購入の仕方を総当たりすればよい。
満点を取るにはNが最大100なので総当たりはできない。

そこでEditorialを見て回答。

求める最大値をx、すなわち取得・購入した経験値・アイテムに対してsum(S)/sum(T)==xとする。
任意のアイテムの購入組み合わせに対しsum(S)/sum(T)≦xなので、変形するとsum(S)-sum(T)*x≦0である。

あとはxを二分探索し、上記式を満たす最大値を探したい。
これには以下のようなグラフを作り、最大フローを求めると良い。
まず、sourceから各集合に相当する頂点に対し、容量S[i]の辺を張る。
また、各アイテムからsinkに対し、容量T[i]*xの辺を張る。

さらに、各集合に相当する頂点から、その集合に属するアイテムに対し容量無限の辺を張る。
この最大フローがsum(S)を上回れば、sum(T)*x≧sum(S)なのでsum(S)-sum(T)*x≦0を満たす。

小数の扱いが怖いので、以下のコードは全体を10^6倍した固定小数点を用いて整数で計算している。

int N,M;
ll SS;
int S[200],T[200];
int K[200], A[200][200];

template<class V> class MaxFlow_dinic {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 1100;
	vector<edge> E[MV];
	int itr[MV],lev[MV];
	
	void add_edge(int x,int y,V cap) {
		E[x].push_back((edge){y,(int)E[y].size(),cap});
		E[y].push_back((edge){x,(int)E[x].size()-1,0}); // directed
	}
	
	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);
		}
	}
	
	int dfs(int from,int to,V cf) {
		if(from==to) return cf;
		ITR(e,E[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<ll> base,test;

bool okok(ll mul) {
	int i;
	test=base;
	FOR(i,M) test.add_edge(200+i,301,T[i]*mul);
	ll res=test.maxflow(0,301);
	return res>=SS;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) cin>>S[i], S[i]*=1000000, base.add_edge(0,i+1,S[i]), SS+=S[i];
	FOR(i,M) cin>>T[i];
	FOR(i,N) {
		cin>>K[i];
		FOR(j,K[i]) cin>>A[i][j],A[i][j]--,base.add_edge(1+i,200+A[i][j],1LL<<60);
	}
	
	ll mi=0;
	for(i=50;i>=1;i--) if(!okok(mi+(1LL<<i))) mi+=1LL<<i;
	_P("%.12lf\n",mi/1000000.0);
}

まとめ

これ系の値仮決め＋二分探索、苦手なので慣れないとなぁ。