これは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); } }
まとめ
トポリジカルソートのライブラリがなかったので、良い機会に作ってみた。