SRM549 Div1 Easy - PointyWizardHats

問題

円錐状の帽子を2つ組み合わせて魔女の帽子を作りたい
上側用の帽子がn個、下側用の帽子がm個ある
上側用の帽子iと下側用の帽子jは以下の条件を満たすときのみ組み合わせて魔女の帽子にできる
1) 上側の帽子の頂点は下側の帽子の頂点より上にある
2) 下側の帽子が上側の帽子に完全に隠れていない
n+m個の帽子をうまくペアにすることで最大で何個の魔女の帽子が作れるか

1 <= n, m <= 50
1 <= (各帽子の高さと半径) <= 10^4

解法

2組の帽子がペアにできる条件は、上側の帽子の高さと半径をha, ra、下側のそれらをhb, rbとすると、
1) hb*ra < ha*rb
2) ra < rb
という式で表せることが図↓からわかる

↑の判定でペアにできる帽子同士を辺で結び、できた二部グラフの最大マッチングをDinicとかで求めればok

class PointyWizardHats {
public:
	int getNumHats(vector<int> ha, vector<int> ra, vector<int> hb, vector<int> rb) {
		int n = ha.size(), m = hb.size();
		Dinic din;
		rep(i,n) din.add_edge(0,100+i,1);
		rep(i,m) din.add_edge(200+i,300,1);
		rep(i,n) rep(j,m) if (ra[i]<rb[j] && hb[j]*ra[i]<ha[i]*rb[j])
			din.add_edge(100+i,200+j,1);
		return din.getflow(0,300);
	}
};