ARC095 E - Symmetric Grid

問題

H行W列のマス目の各マスに英小文字が書かれている
任意の異なる2行/列をswapするという操作を何度でも行えるとき、マス目が点対称になるようにできるか判定
H,W <= 12

解法

行のswapと列のswapは可換
行のswapの仕方が決まっているとき、列をうまくswapして条件を満たせるかの判定は、"片方の列を上下反転すると他方の列に一致する"ような2列をペアにしていき、全ての列がペアになればok
ただし列数Wが奇数のときはペアが(W-1)/2個できた上で余った1列が上下対象なら(その列を真ん中にすれば)ok
これはO(HW^2)でできる

で行のswapの仕方が問題で、普通に全部試そうとすると最大O(H!)になる
でも考えてみると、"ある状態のマス目" が↑の列のswapで条件を満たせる[満たせない]なら "そのi(1-based)行目をH-i行目とswapしたマス目" でも条件を満たせる[満たせない]ことがわかる
だから12!通り試す必要はなく、各行に対応させる(ちょうど反対側に置く)行を全通り試すだけでいい
そうすればH=12のときでも11*9*7*5*3 = 10395通りしかない

実装

enu)
ここで行の対応関係を作ってる
i行目のペアを決めたかどうかをbのiビット目で管理
x[i]とy[i]がペア
ただし行数が奇数のときは最初にどの行を孤立させるか選んでxの先頭に入れる
後で実際に行を並び替えた文字列を作る時やりやすいようにjudgeに飛ぶ直前にxを反転してる

judge)
↑で並び替えたものが列のswapで条件を満たせるかチェックする
全部ペアにできたら問題なくYES
列数が奇数で1列だけ余った場合(p+1==wのとこ)は、その孤立した列が回分になってたらYES

もうちょいわかりやすく書けた気がする
これ書いた時すごい眠かった

int h, w;
string s[12];

void judge(vector<int> x, vector<int> y) {
	string t[12] = {};
	rep(i,x.size()) rep(j,w) t[j].push_back(s[x[i]][j]);
	rep(i,y.size()) rep(j,w) t[j].push_back(s[y[i]][j]);
	bool ok[12] = {};
	rep(i,w) if (!ok[i]) {
		string r = t[i];
		reverse(all(r));
		reps(j,i+1,w) if (!ok[j] && r==t[j]) {
			ok[i] = ok[j] = 1;
			break;
		}
	}
	int p = accumulate(ok,ok+w,0), fin = 0;
	if (p==w) fin = 1;
	if (p+1==w) rep(i,w) if (!ok[i]) {
		string r = t[i];
		reverse(all(r));
		if (r==t[i]) fin = 1;
	}
	if (fin) {
		cout << "YES";
		exit(0);
	}
}

void enu(int b, vector<int> x, vector<int> y) {
	int p = __builtin_popcount(b);
	if (p==h) {
		reverse(all(x));
		judge(x,y);
		return;
	}
	if (h%2 && p==0) {
		rep(i,h) {
			x.push_back(i);
			enu(b|(1<<i), x, y);
			x.pop_back();
		}
		return;
	}
	vector<int> t;
	rep(i,h) if (~b>>i&1) t.push_back(i);
	reps(i,1,h-p) {
		x.push_back(t[0]), y.push_back(t[i]);
		enu(b|(1<<t[0])|(1<<t[i]), x, y);
		x.pop_back(), y.pop_back();
	}
}

int main() {
	cin >> h >> w;
	rep(i,h) cin >> s[i];
	vector<int> X, Y;
	enu(0,X,Y);
	cout << "NO";
}