ARC095 E : Symmetric Grid(700)
作成日：2018.09.09
最終更新日：2018.09.09
問題概要
$H$行$W$列のマス目に英小文字が書かれている。
操作「2つの異なる行または列を選び入れ替える」を繰り返すことで、マス目を点対称にできるかを判定せよ。
制約
$1 \leq H,W \leq 12$
考え方
行に対する操作と列に対する操作は順序によらず同じ結果を与えるので、これらを分けて考えることができる。
まず、行に対してのみ操作を行うことを考える。
点対称にするためにはマス$(i,j)$,$(H-1-i,W-1-j)$に書かれている文字を同じにすれば良い。
$j$や$W-1-j$を変えないでこれを満たすには、書かれている文字の順が逆である2つの行を$i$行目と$(H-1-i)$行目におけば良い。
$i$をいくつにするかについては制約がないので、すべての行を書かれている文字の順が逆であるものと重複なくペアにできるかを判定すれば良い。
但し、$H$が奇数の時は自分自身とペアになる行が1つだけ存在する。
この判定は、まだペアになっていない行を1つ選び、それと逆順である行があればそれとペアにすることを繰り返すことで行える。
愚直にやっても計算量は$O(H^2W)$である。
後は列の並び替えを行えば良いが、すべて試すと$W!$通りあるので工夫する。
マス$(i,j)$,$(H-1-i,W-1-j)$が等しいかのみが重要だが、$j$と$W-1-j$を入れ替えて判定しても問題はない。
さらに$j$をすべて別の同じもので置き換えて判定しても問題はない。
すなわちどの2つの列がペアになるかだけを全列挙すれば良い。
ペアの組み合わせ方は$(W-1)!!$通りで高々$10395$通りしかない。
よってこれらすべてを試すことができる。
ソースコード
マクロ等はこちら
int H,W;
string S[12];
int p[12];
bool q[12];
bool check(){
bool b[12] = {};
bool c = H&1;
repp(i,0,H) if(!b[i]){
repp(j,i+1,H) if(!b[j]){
repp(k,0,W){
if(S[i][p[k]] != S[j][p[W-1-k]]) break;
if(k+1 == W) b[i] = b[j] = 1;
}
if(b[j]) break;
}
if(!b[i]){
if(c){
repp(k,0,W) if(S[i][p[k]] != S[i][p[W-1-k]]) return 0;
c = 0;
} else return 0;
}
}
return 1;
}
bool solve(int a , int n , bool b){
if(a == W) return check();
if(q[a]) return solve(a+1,n,b);
if(b){
p[W/2] = a; q[a] = 1;
if(solve(a+1,n,0)) return 1;
q[a] = 0;
}
repp(i,a+1,W) if(!q[i]){
p[n] = a; p[W-1-n] = i;
q[a] = q[i] = 1;
if(solve(a+1,n+1,b)) return 1;
q[a] = q[i] = 0;
}
return 0;
}
int main(){
cin >> H >> W;
repp(i,0,H) cin >> S[i];
cout << (solve(0,0,W&1)?"YES":"NO") << endl;
return 0;
}解法まとめ
列の並べ方は、線対称の位置にあるものをペアとした時、ペアの組み方を全列挙するようにする。(27-42行)
列の並べ方それぞれにおいて、すべての行を書かれている文字の順が逆であるものと重複なくペアにできるかを判定する。
但し、$H$が奇数の時は1つだけ自分自身とペアになるものがあることに注意する。(6-25行)
1つでも可能な列の並べ方があればYES、そうでなければNOが答えである。(47行)