Codeforces #163 Div2. C. Below the Diagonal

さて3問目。
本番は少しCを見て、その後しばらくDに挑み、またCに戻ってきたのでだいぶ回答がおくれてしまった。
http://codeforces.com/contest/266/problem/C

NxN行列のうち、N-1個の要素が1でその位置が与えられる。それ以外の要素は0である。
この時、行の入れ替えおよび列の入れ替えを行い、1を対角成分の左下側に寄せる。
そのような入れ替え手順例を答える問題。
入れ替え回数は最小でなくてもよい。

N<=1000で、入れ替え上限は100000なので、入れ替え回数はO(N^2)以下に抑えないといけない。

これはどうやれば1を左下に寄せられるかを考えるのが面白い問題。
色々考えた結果自分は以下の様に行った。

まず第１ステップでは、行の入れ替えを行っていく。
行ごとの1の数をカウントし、選択ソートの要領で1が多い行から順に下に配置していく。
比較回数はO(N^2)だけど入れ替えはN回以下ですむ。

次に第２ステップでは、列の入れ替えを行っていく。
こちらは列ごとに1がある最上位の位置を調べ、また選択ソートの要領で1が高い順に左に配置していく。
こちらも比較がO(N^2)、入れ替えはN回以下。

これで、２ステップを合わせても比較はO(N^2)、入れ替えは2N回で処理可能となる。

int N;
int mat[1001][1001];
int nh[1001],ny[1001];
vector<pair<int, int> > step;

void solve() {
	int f,r,i,j,k,l,x,y;
	
	ZERO(mat);
	N=GETi();
	
	FOR(i,N-1) {
		y=GETi()-1;
		x=GETi()-1;
		mat[x][y]=1;
		ny[y]++;
	}
	
	//tate
	for(y=N-1;y>=0;y--) {
		int nc=0,my=-1;
		int ty;
		FOR(ty,y+1) {
			if(ny[ty]>nc){ nc=ny[ty]; my=ty;}
		}
		if(nc==0) break;
		if(my<y) {
			step.push_back(make_pair(1,my*1000+y));
			swap(ny[my],ny[y]);
			FOR(x,N) swap(mat[x][y],mat[x][my]);
		}
		
	}
	//yoko
	FOR(x,N) nh[x]=N;
	FOR(x,N) for(y=N-1;y>=0;y--) if(mat[x][y]) nh[x]=y;
	
	FOR(x,N) {
		int nc=N+1,mx=-1;
		int tx;
		for(tx=x;tx<N;tx++) {
			if(nh[tx]<nc){ nc=nh[tx]; mx=tx;}
		}
		if(mx==-1) break;
		if(mx!=x) {
			step.push_back(make_pair(2,mx*1000+x));
			swap(nh[mx],nh[x]);
		}
	}
	
	_P("%d\n",step.size());
	FOR(i,step.size()) _P("%d %d %d\n",step[i].first,1+step[i].second/1000,1+(step[i].second%1000));
	
	return;
}

まとめ

なかなか面白い問題だった。
CodeforceはTopCoderと違い、正解時のスコアがコンテスト開始からの時間で決まるから解く順番の選択が重要だな…。