TopCoder SRM 702 Div1 Easy GridSortMax

朝会なので不参加。Easyは一発で通せたので出たかったな。
https://community.topcoder.com/stat?c=problem_statement&pm=14444

問題

H*Wのグリッドがあり、各セル1～(H*W)の値が1個ずつ入っている。
隣接する列または行を入れ替えるという処理を繰り返し、1行目に1～W、2行目に(W+1)～2*W…と並べるようにしたい。
そのように並べられたセルを1、並べられないセルを0とし、各セルの値を文字列として連結するとする。

得られる辞書順最大の文字列を答えよ。

解法

辞書順最大のものを答えるので、先頭から順に値をそろえていくことを考える。
今値xを希望の位置に移動したいとする。
x未満の値ですでに希望の位置にあるセルがある場合、それをずらすと「辞書順最大」を達成できないので、その行・列は入れ替えることができない。
逆にそれ以外の行・列は入れ替え可能である。(途中に入れ替え不可な行・列があっても、よい)

あとは貪欲に入れ替え可能な範囲で値をそろえていくだけ。

class GridSortMax {
	public:
	int A[51][51];
	int R[51*51];
	int H,W;
	int NGR[51],NGC[51];
	
	string findMax(int n, int m, vector <int> grid) {
		int y,x,y2,x2;
		H=n;
		W=m;
		
		ZERO(NGR);
		ZERO(NGC);
		
		FOR(y,H) FOR(x,W) A[y][x]=grid[y*W+x]-1, R[grid[y*W+x]-1]=y*100+x;
		
		FOR(y,H) FOR(x,W) {
			int cy=R[y*W+x]/100;
			int cx=R[y*W+x]%100;
			int ng=0;
			if(y!=cy && (NGR[y]||NGR[cy])) continue;
			if(x!=cx && (NGC[x]||NGC[cx])) continue;
			
			FOR(x2,W) {
				swap(A[y][x2],A[cy][x2]);
				R[A[y][x2]]=y*100+x2;
				R[A[cy][x2]]=cy*100+x2;
			}
			FOR(y2,H) {
				swap(A[y2][x],A[y2][cx]);
				R[A[y2][x]]=y2*100+x;
				R[A[y2][cx]]=y2*100+cx;
			}
			
			NGR[y]=NGC[x]=1;
		}
		
		string S;
		FOR(y,H) FOR(x,W) S+=(A[y][x]==y*W+x)+'0';
		return S;
		
	}
}

まとめ

Div2 Mediumの方が手間取った。