kmjp's blog

競技プログラミング参加記です

TopCoder SRM 740 Div2 Hard EvenMatrices

定番テクを知っていると非常に簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=15140

問題

R*Cの大きさの0/1の2値からなる行列を考える。
このうち、各行・各列における1の登場数が偶数であるものを辞書順昇順に並べたとき、K番目に来るのはどれか。

解法

行・列それぞれパリティが0になっていなければならないという条件が厄介。
ただこれは対応が容易で、左上(R-1)列(C-1)行は何でもよく、そこを決めると最右列・最下段が確定する。

よって左上(R-1)列(C-1)行を合わせて(R-1)*(C-1)桁の2進数とみなしたときそれがKとなるように1を入れていけばよい。
あとは最右列・最下段を埋めよう。

class EvenMatrices {
	public:
	vector <string> findKth(int r, int c, long long k) {
		vector<string> V,E;
		int y,x;
		FOR(y,r) V.push_back(string(c,'0'));
		int left=(r-1)*(c-1);
		
		FOR(y,r-1) FOR(x,c-1) {
			left--;
			if(left>60) continue;
			if(k>=1LL<<left) {
				V[y][x]^=1;
				V[r-1][x]^=1;
				V[y][c-1]^=1;
				V[r-1][c-1]^=1;
				k-=1LL<<left;
			}
		}
		
		return k?E:V;
		
	}
}

まとめ

パリティ指定のある行列は、(R-1)行(C-1)列は何でもよい、というテクは定番なので使えるようになっておこう。