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"; }