何か同じやり方の人が見当たらなかったので
問題概要
\(H \times W\)のグリッドが与えられる．各マスには文字が書いてある．行と列を適当に並べ替えて，グリッドを点対称にできるか？
制約: \(H, W \leq 12\)
解法
まずグリッドを入れ替えるやつは行と列を独立に考えられるというのは典型．制約がかなり小さいから，bitや順列の探索をするんだろうとも思う．そこで，列の並べ方を固定してから，行を並べ替えて点対称にできるか判定するという方針が立つ．行を並べ替えて点対称にできるかの判定は公式解説と同様に\(O(H^2W)\)でできる．
列の並べ方の探索を考える．当然\(W \leq 12\)なので\(O(W!)\)は間に合わない．ここで，ある点対称なグリッドがあったときに，その列を左右対称に並べ替えても点対称なままであることがわかる（例えば，\(W=12\)で，1列目と3列目，10列目と12列目を入れ替えるなど）．よって，列を左右に振り分けた後は，左半分は固定して，右半分の順列だけ全探索すればよい．列を左右に振り分けるのはbit全探索を用いて\(O\left(\binom{W}{\frac{W}{2}}\right)\)，片側の順列の全探索は\(O\left(\left(\frac{W}{2}\right)!\right)\)でできる．よって列の並べ方の探索は全体で\(O\left(\frac{W!}{\frac{W}{2}!}\right)\)．\(\frac{12!}{6!} = 665280\)で，行の並べ替えのパートも合わせると大体\(10^9\)くらいになり，通る．さすがにPyPyだと厳しかったが，定数倍重い処理は多分ないし，軽く枝刈りはしているのでC++だと通る．
全体の計算量は\(O\left(\frac{W!}{\frac{W}{2}!}H^2W\right)\)．こんな計算量見たことね～これが書きたかったからこの記事をわざわざ書いたみたいなところはある．
ところで公式解説は，列の並べ替えのところでどの2つをペアにするかを全探索しているので，\(O((W - 1)!!)\)になっている．\(11!! = 10395\)だから僕のより約60倍速い．計算量が二重階乗になるのも初めてみた．
実装は見た目ほど重くない．
提出
atcoder.jp
