Codeforces ECR #008 : F. Bear and Fair Set

想定解以外の解法だと、D,Eよりずっと楽なんですが…。
http://codeforces.com/contest/628/problem/F

問題

1～Bの整数のうち、N個を選びたい。
その時以下の条件を満たすようにしたい。

• Nは5の倍数である。選んだ数字のうち、5で割った余りが0,1,2,3,4となるものがN/5個ずつあるようにしたい。
• 条件がいくつか与えられる。各条件は(U[i],Q[i])で表現され、選んだ値のうちU[i]以下のものがQ[i]個あることを示す。

条件を満たす選び方は存在するか判定せよ。

解法

条件に(0,0)と(B,N)を加えておこう。
その上で条件をU[i]の値で昇順ソートする。

あとはグラフの問題として解く。

まず前者の条件を処理するため、以下のようなグラフを作る。

• sourceから、5個の頂点にN/5の容量の辺を張る(余りが0～4のものに対応する)
• 選んだ数値1～Bに対応する点を作る。前述の5個の頂点のうち数値を5で割った余りに対応する点から、各数値に容量1の辺を張る。
• 隣接するクエリ(U[i],Q[i]),(U[i+1],Q[i+1])を考えると、(U[i]+1)～(U[i+1])の間の整数からQ[i+1]-Q[i]個選ぶことになる。
  • そこで、前述の1～Bに対応する点のうち、(U[i]+1)～(U[i+1])の頂点から、クエリ毎に作った頂点に容量1の辺を張る。またこのクエリ毎の頂点からsinkに容量(Q[i+1]-Q[i])の辺を張る。

あとはこのグラフでNのフローを流せれば条件を満たせる。

int N,B,Q;
pair<int,int> P[10101];

template<class V> class MaxFlow_Ford {
public:
	struct edge { int to,reve;V cap;};
	static const int MV = 40000;
	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<int> mf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>B>>Q;
	FOR(i,Q) cin>>P[i].first>>P[i].second;
	P[Q].first=P[Q].second=0;
	P[Q+1].first=B;
	P[Q+1].second=N;
	Q+=2;
	sort(P,P+Q);
	
	FOR(i,5) mf.add_edge(0,10+i,N/5);
	
	for(i=1;i<=B;i++) mf.add_edge(10+i%5,100+i,1);
	for(i=1;i<Q;i++) {
		for(x=P[i-1].first+1;x<=P[i].first;x++) mf.add_edge(100+x,10200+i,1);
		if(P[i].second<P[i-1].second) return _P("unfair\n");
		mf.add_edge(10200+i,20400,P[i].second-P[i-1].second);
	}
	if(mf.maxflow(0,20400)==N) cout<<"fair"<<endl;
	else cout<<"unfair"<<endl;
	
	
}

まとめ

Editorialの解法を理解していない…。