Codeforces #659 Div1 D. Rearrange

問題文の理解に手間取る。
http://codeforces.com/contest/1383/problem/D

問題

N*Mの行列Aが与えられる。
Aの要素中には、1～NMの値が1回ずつ現れる。

以下を満たすA'を構築せよ。

• Aと同じサイズで、やはり1～NMで構成される。
• 各行ベクトルにおいて、値が降順である。
• 各列ベクトルにおいて、値が降順である。
• AとA'でスペクトルが等しい。スペクトルとは、各行の最大値からなる集合と、各列の最大値からなる集合である。

解法

値の大きい順に入れていく。
スペクトルの情報から、列または行が確定する場合は、そこに入れる。
この作業により、「列または行の最大値が確定したので、それより小さい値は以後任意の値を入れられる要素」というものが生じる。
スペクトルから情報が得られない場合、そのような場所に埋めて行こう。

int H,W;
int A[303][303];
int B[303][303];
int R[303],C[303];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		FOR(x,W) {
			cin>>r;
			R[y]=max(R[y],r);
			C[x]=max(C[x],r);
		}
	}
	
	int CH=0,CW=0;
	queue<pair<int,int>> Q;
	for(i=H*W;i>=1;i--) {
		int inR=count(R,R+H,i);
		int inC=count(C,C+W,i);
		if(inR) CH++;
		if(inC) CW++;
		if(inR||inC) {
			B[CH-1][CW-1]=i;
		}
		else {
			y=Q.front().first;
			x=Q.front().second;
			B[y][x]=i;
			Q.pop();
		}
		
		if(inR) {
			for(x=CW-2;x>=0;x--) Q.push({CH-1,x});
		}
		if(inC) {
			for(y=CH-2;y>=0;y--) Q.push({y,CW-1});
		}
	}
	
	FOR(y,H) {
		FOR(x,W) cout<<B[y][x]<<" ";
		cout<<endl;
	}
		
	
	
	
}

まとめ

これBぐらいで出ても不思議じゃない難易度だ。