ARC 095 E - Symmetric Grid - ツバサの備忘録

解法

それぞれの行に含まれている文字の種類とその個数の状態関係について見てみると、
行をswapしても、列をswapしても、個数自体に変化はないことがわかります。
最終的に点対称になるので、先ほどの状態の一致不一致を使って、行と列それぞれで回文を作れることが必要になってきます(これは必要条件であり、十分条件ではありません)。
この条件で網羅しきれない入力は以下のようなものです:

3 4
abba
cddc
baab

行についてみると、文字の状態が既に対照的になっていることがわかります。列についても同様です。しかし、これは点対称になっておらず、回転させると四つ角が一致しません。
ところで、入力についてよく見てみると、行数は12ととても少ないことがわかります。 $H/2$ 個のペアを作る、ということを列挙することを考えると、 $H=12$ であった場合、
$\frac{12 \times 11}{2} \times \frac{10 \times 9}{2} \times \frac{8 \times 7}{2} \times \frac{6 \times 5}{2} \times \frac{4 \times 3}{2} \times \frac{2 \times 1}{2} \times \frac{1}{6!} = 11!! = 10395$
通りとなります。実際にDFSでペアを作成するときは、まだペアにしていないもののうち、片方は行番号が一番小さいものを必ず使う、とすることで無駄なく列挙できます。
点対称にするためには、 $W/2$ 個の列番号のペア $(i,j)$ を作成し、今作成した全てのペア(奇数で漏れたものについては自分自身)について、ペアの文字列が $s$ と $t$ だった場合に、 $s_{i} = t_{j}$ かつ $s_{j} = t_{i}$ となる必要があります。
逆に、これができれば点対称にすることができます。
この判定は、行のペアを決めた後、全ての行ペアに対して条件を満たすような列ペアを辺で結んだグラフを考えると、連結成分のサイズが奇数になっているものの数が1以下になっているかどうかでできます。
全ての行ペアの決め方に対して、上記の判定を行い、1つでも1以下のものがあればYES、そうでなければNOになります。