Codeforces #168 Div1 D. Lovely Matrix

これは最終的に自分で答えにたどり着けた。
http://codeforces.com/contest/274/problem/D

問題

NxMの行列があり、各要素が整数で与えられる。
ただし一部の要素は値が不明である。

この行列に対し、任意の列同士を並べ替えることで、各行が単調増加になるようにしたい。
そのようにできるか、できるなら列の順番を答えよ。

解法

ちょうど先日のCF264に近い問題があった。
Codeforces #264 Div2 D. Gargari and Permutations - kmjp's blog
ただ、これと同じ解法を取ろうとするとO(N*M^2)かかりTLEする。

今回は列の昇順に並べる問題なので、列同士の大小関係を求めてトポロジカルソートをすればよい。
ただ、辺の数を減らさないと間に合わないので辺を減らすことを考える。

まず、各行における列同士の大小関係を辺にする際、隣接する列以外は辺を張る必要がない。
例えばある行で数字をソートすると2 5 10 14のように並んだら、2と5の列、5と10の列、10と14の列、と辺を張ればよく、列同士の全組み合わせについて辺を張る必要はない。
同じ数字が多いとき、たとえば3 3 3 3 4 4 4 4 4のような場合、このままだと4*5で20本辺を引くことになるが、間に仮の点を入れ3 3 3 3 3.5 4 4 4 4 4のように考えると辺が9本で済む。

上記のように辺を減らすと、結局N頂点・N*M辺のトポロジカルソートなので十分間に合う。

int N,M,T;
set<int> E[200010];
vector<int> R;
int in[200010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	T=M;
	FOR(i,N) {
		map<int,vector<int> > MM;
		FOR(x,M) {
			cin>>y;
			if(y!=-1) MM[y].push_back(x);
		}
		if(MM.size()<2) continue;
		map<int,vector<int> >::iterator it1,it2;
		for(it2=MM.begin(),it1=it2++;it1!=MM.end()&&it2!=MM.end();it1++,it2++) {
			vector<int> &v1=it1->second,&v2=it2->second;
			if(v1.size()<=2 || v2.size()<=2) {
				FOR(x,v1.size()) FOR(y,v2.size()) E[v1[x]].insert(v2[y]);
			}
			else {
				FOR(x,v1.size()) E[v1[x]].insert(T);
				FOR(y,v2.size()) E[T].insert(v2[y]);
				T++;
			}
		}
	}
	
	queue<int> Q;
	FOR(i,T) ITR(it,E[i]) in[*it]++;
	FOR(i,T) if(in[i]==0) Q.push(i);
	while(!Q.empty()) {
		int cur=Q.front();
		Q.pop();
		if(cur<M) R.push_back(cur);
		ITR(it,E[cur]) if(--in[*it]==0) Q.push(*it);
	}
	
	if(R.size()<M) return _P("-1\n");
	FOR(i,M) _P("%d ",R[i]+1);
	_P("\n");
}

まとめ

大小関係の辺を減らすために間に仮の頂点を入れるテク、以前も出たはずなのにしばらく忘れてた。