あまりいい方法ではないが。
https://beta.atcoder.jp/contests/arc095/tasks/arc095_c
問題
H*Wのグリッドの各セルに文字が配置されている。
2つの列または2つの行を入れ替えることを繰り返し、文字の配置を点対象にできるか。
解法
上半分の行の並び順を総当たりしよう。
下半分は余った行を適当に(例えば元の行の昇順に)入れることを考える。
あとは列の入れ替えにより全体を点対象にするわけだが、列方向に見てW個のH文字の文字列があるとき、互いに反転すると一致するものを2個ずつペアにしていく問題となる。
(Wが奇数のときは中央の1個を除き)全体をペアで組めれば題意を満たす。
以下のコードは割と定数倍高速化でゴリ押している。
int W,H; string S[12]; string T[12],R[12]; int num=0; void hoge() { int x,y; set<string> U; int left=0; FOR(x,W) { if(U.count(R[x])) { U.erase(R[x]); } else { U.insert(T[x]); } } if(U.empty()) { cout<<"YES"<<endl; exit(0); } if(U.size()==1) { string s=*U.begin(); string t=s; reverse(ALL(s)); if(t==s) { cout<<"YES"<<endl; exit(0); } } } void add(int l) { int x; FOR(x,W) { T[x].push_back(S[l][x]); R[x][H-T[x].size()]=S[l][x]; } } void del() { int x; FOR(x,W) T[x].pop_back(); } void dfs(int mask,int last) { int i; if(__builtin_popcount(mask)>=(H+1)/2) { int num=0; FOR(i,H) { if((mask&(1<<i))==0) { num++; add(i); } } hoge(); FOR(i,num) del(); return; } FOR(i,H) if((mask&(1<<i))==0) { add(i); dfs(mask^(1<<i),i); del(); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; FOR(x,W) R[x].resize(H); FOR(y,H) cin>>S[y]; vector<int> V; dfs(0,-1); cout<<"NO"<<endl; }
まとめ
どこが想定解との差分なんだろう。