TopCoder SRM 635 Div1 Medium StoryFromTCO

前回に引き続き、「考え方自体ダメだけど、考え方が合っててもライブラリがダメダメだった」という残念な回。
http://community.topcoder.com/stat?c=problem_statement&pm=13412

問題

N個の問題がある。
それぞれでcutoff[i]以内の順位に入りたい。
今、各問題の順位にはplace[i]となることがわかっている。

ここで、不思議なトリックを使うことで、ある問題の自分の順位を別の問題の自分の順位と入れ替えることできる。
全問題でcutoff[i]以内に入るには、最小何か所の問題で順位入れ替えが必要か。

解法

自分のやったTLEダメ解法。
ある問題の順位が、どこの問題であればcutoff[i]内に入れるかによってコスト付フローを作り、最小コストフローを求める。
place[x]≦cutoff[y]なら、x→1000+yに容量1の辺を張り、そのコストはx==yなら0、x!=yなら1とすればよい。
ただし、この手法は最悪O(N^2)の辺ができるため、TLEしてしまう。

そこで辺を減らす方法として、zerokugi氏のツイートを参考にした。
https://twitter.com/zerokugi/status/518466336737865729

始点終点以外に2*N個の頂点を設けてグラフを作る。

• 各頂点xに対し、source→x及び1000+x→sinkにコスト０容量１の辺を張る。
• place[x]≦cutoff[x]ならx→1000+xにコスト０容量１の辺を張る。
• 上記まではさほど特別なことはないが、ここでzerokugi氏の方式を利用する。
  • cutoff順でソートした頂点番号順をV[x]とすると、1000+V[i]→1000+V[i+1]に容量無限大でコスト0の辺を張る
  • place[x]≦cutoff[V[i]]となる最小のiに対し、x→1000+V[i]にコスト１容量１の辺を張る。

元のグラフではplace[x]≦cutoff[y]な頂点対にかたっぱしから辺を張っていたが、こちらはplace[x]≦cutoff[V[i]]な頂点対にしか辺を張らないため、全体で辺の数はO(N)で済む。

なお、辺を減らしても自分のダメ最小コストフローライブラリではTLEしたので、priority_queueを使って改善した。

template<int NV,class V> class MinCostFlow {
public:
	struct edge { int to, capacity; V cost; int reve;};
	vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV];
	void add_edge(int x,int y, int cap, int cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	V mincost(int from, int to, int flow) {
		V res=0; int i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, numeric_limits<V>::max()/2);
			dist[from]=0;
			priority_queue<pair<int,int> > Q;
			Q.push(make_pair(0,from));
			while(Q.size()) {
				int d=-Q.top().first, cur=Q.top().second;
				Q.pop();
				if(dist[cur]!=d) continue;
				if(d==numeric_limits<V>::max()/2) break;
				FOR(i,E[cur].size()) {
					edge &e=E[cur][i];
					if(e.capacity>0 && dist[e.to]>d+e.cost) {
						dist[e.to]=d+e.cost;
						prev_v[e.to]=cur;
						prev_e[e.to]=i;
						Q.push(make_pair(-dist[e.to],e.to));
					}
				}
			}
			
			if(dist[to]==numeric_limits<V>::max()/2) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

int N;
class StoryFromTCO {
	public:
	int minimumChanges(vector <int> places, vector <int> cutoff) {
		N=places.size();
		int i,j,x,y;
		pair<int,int> P[1001];
		FOR(i,N) P[i]=make_pair(cutoff[i],i);
		sort(P,P+N);
		
		MinCostFlow<2040,int> mcf;
		
		FOR(i,N) mcf.add_edge(0,10+i,1,0);
		FOR(i,N) mcf.add_edge(1020+i,1,1,0);
		FOR(i,N) if(places[i]<=cutoff[i]) mcf.add_edge(10+i,1020+i,1,0);
		FOR(i,N-1) mcf.add_edge(1020+P[i].second,1020+P[i+1].second,1000,0);
		
		FOR(x,N) {
			FOR(y,N) if(places[x]<=P[y].first) break;
			if(y<N) mcf.add_edge(10+x,1020+P[y].second,1,1);
		}
		return mcf.mincost(0,1,N);
	}
}

まとめ

本番単純な最小コストフローを書いて失敗してしまった。
計算量をちゃんと見積もらねば。

それにしても最近Div1Mediumはグラフ問題多くない？