Codeforces #707 Div1 : C. Matrix Sorting

本番ちょっと手間取ったけどどうにか解けた。
https://codeforces.com/contest/1500/problem/C

問題

2つの行列A,Bが与えられる。
Aのうち列を1つ選び、その列の値が各行で昇順となるよう、行単位の並べ替えを行うことを考える。
AをBに一致させられるか、またその時の手順を答えよ。

解法

まず、Aの行を並べ替えるたものがBと一致することを確認しよう。
あとはその手順を考える。

Aの初期状態は無視して、各列を1回ずつ選択し、Bとなるパターンを考えよう。
ここで、Bから逆に巻き戻すことを考える。

Bを各列で見たとき、途中で値が昇順から崩れている場合、その列はまだ選択してはいけないことを示す。
トポロジカルソートの要領で、選択できる列とその順番を絞り込んでいこう。

int H,W;
vector<int> A[1515],B[1515];
map<vector<int>,int> M;

int T[1515];
int C[1515];
vector<int> D[1515];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&H,&W);
	FOR(y,H) {
		A[y].resize(W);
		FOR(x,W) scanf("%d",&A[y][x]);
		M[A[y]]++;
	}
	
	FOR(y,H) {
		B[y].resize(W);
		FOR(x,W) scanf("%d",&B[y][x]);
		M[B[y]]--;
		if(M[B[y]]<0) return _P("-1\n");
	}
	
	vector<int> ret;
	queue<int> Q;
	FOR(x,W) {
		FOR(y,H-1) if(B[y][x]>B[y+1][x]) C[x]++, D[y].push_back(x);
		if(C[x]==0) Q.push(x);
	}
	while(Q.size()) {
		x=Q.front();
		ret.push_back(x);
		Q.pop();
		FOR(y,H-1) if(B[y][x]<B[y+1][x]) {
			FORR(r,D[y]) {
				C[r]--;
				if(C[r]==0) Q.push(r);
			}
			D[y].clear();
		}
		
	}
	
	if(ret.size()!=W) return _P("-1\n");
	cout<<ret.size()<<endl;
	reverse(ALL(ret));
	FORR(r,ret) cout<<(r+1)<<" ";
	cout<<endl;

}

まとめ

最初横着して計算量にlogをつけてしまったせいでTLEを連発してしまった。