kmjp's blog

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

Maximum-Cup 2013 : H - さいたまの矛盾

これはTwitterのTLで「トポロジカルソートじゃね?」というヒントをもとに解いてみた。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_h

問題

1~Nの番号を持つN人の人がいる。各人はそれぞれ異なる強さを持つ。
また、各人の強弱関係は推移律を満たす。

以下の条件が最大M個与えられるとき、何番目の条件まで矛盾なく満たせるか答えよ。

  • P番の人はL~R番の人より強い
  • P番の人はL~R番の人より弱い

解法

Q番目までの条件が満たせる、と仮定して二分探索をしてQを求めていく。

Qを定めたら、1~Q番目の条件文に則り強弱関係をグラフの辺として張っていく。
得られたグラフがトポロジカルソートができたらその条件までを満たすことができる。

二分探索でなく、1番目から順々に条件を追加した場合、グラフの構築は速くなるがトポロジカルソートの回数が増え、結果的にTLEしてしまった。

int N,M;
int P[1001],L[1001],R[1001];
char C[1001];
map<int,int> UN;

class TopologicalSort {
public:
	static const int MV = 10000;
	int NV,NIE[MV];
	vector<int> OutEdge[MV];
	
	TopologicalSort(int nv){init(nv);}
	void init(int nv) { NV=nv; for(int i=0;i<NV;i++) OutEdge[i].clear(), NIE[i]=0;}
	void add_edge(int x,int y) { OutEdge[x].push_back(y); NIE[y]++;}
	
	vector<int> sort() {
		int i,nv=0;
		vector<int> NI,R;
		NI.reserve(NV);
		R.reserve(NV);
		queue<int> S;
		FOR(i,NV) {
			NI.push_back(NIE[i]);
			nv+=OutEdge[i].size();
			if(NIE[i]==0) S.push(i);
		}
		
		while(!S.empty()) {
			int cur=S.front();
			S.pop();
			R.push_back(cur);
			ITR(it,OutEdge[cur]){
				nv--;
				if(--NI[*it]==0) S.push(*it);
			}
		}
		if(nv) return vector<int>();
		return R;
	}
};

int check(int pi) {
	int i,j;
	TopologicalSort ts(N);
	FOR(i,pi) {
		for(j=UN[L[i]];j<=UN[R[i]];j++) {
			if(C[i]=='w') ts.add_edge(j,UN[P[i]]);
			else ts.add_edge(UN[P[i]],j);
		}
	}
	
	return !ts.sort().empty();
}

void solve() {
	int f,i,j,k,l,x,y;
	string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>P[i]>>C[i]>>L[i]>>R[i];
		UN[P[i]]=UN[L[i]]=UN[R[i]]=0;
	}
	N=0;
	ITR(it,UN) it->second=N++;
	
	int lo=1,hi=M;
	FOR(k,12) {
		int pi=(lo+hi)/2;
		if(check(pi)) lo=pi;
		else hi=pi;
	}
	
	hi=max(hi-2,0);
	while(1) {
		if(check(hi)==1) {
			if(hi==M) return _P("0\n");
			hi++;
		}
		else return _P("%d\n",hi);
	}
}

まとめ

トポリジカルソートのライブラリがなかったので、良い機会に作ってみた。