AtCoder ARC #054 : C - 鯛焼き

説明が難しい…。
http://arc054.contest.atcoder.jp/tasks/arc054_c

問題

N個のタイヤとN個の木があり、それぞれ相性の良しあしが行列の形で与えられる。
タイヤと木を1対1で対応付け、N個の相性の良いタイヤと木の組み合わせを作りたい。
作り方の総数の偶奇を答えよ。

解法

要は２部グラフに対する完全マッチングの個数の偶奇を答える問題である。
２部グラフの完全マッチングは、結局は要素の並べ替えに相当する。

有効な並べ替え方の総数の計算式を考えると、行列式の計算式に似ていることに気づく。
(1つ列と行の組み合わせ(i,j)を決めると、残りはその余因子行列からまた列と行を取る、というイメージ)
結論としてはGF(2)上で行列式の偶奇を求めればよい。
以下はGF(2)上でランクがNかどうか求めているが、結局は同じことである。

const int MAT=402;
int mat[MAT][MAT];


int gf2_rank(int A[MAT][MAT],int n) { /* input */
	int i,j,k;
	FOR(i,n) {
		int be=i,mi=n+1;
		for(j=i;j<n;j++) {
			FOR(k,n) if(A[j][k]) break;
			if(k<mi) be=j,mi=k;
		}
		if(mi>=n) break;
		FOR(j,n) swap(A[i][j],A[be][j]);
		
		FOR(j,n) if(i!=j&&A[j][mi]) {
			FOR(k,n) A[j][k] ^= A[i][k];
		}
	}
	return i;
}

int N;
string S[303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FOR(x,N) mat[y][x]=S[y][x]=='1';
	}
	if(gf2_rank(mat,N)<N) cout<<"Even"<<endl;
	else cout<<"Odd"<<endl;
	
}

まとめ

これは本番に気づけて良かった。