問題概要

それぞれのマスにアルファベットの小文字が入った，H×W (H, Wは12以下) のマス目が与えられる．行の交換と列の交換を繰り返し，このマス目を点対称にできるか判定する．

解法概要

行の交換と列の交換の操作の順番は変えても問題ないので，行の交換→列の交換と順番を固定する．

行の交換については，全ての行の並べ方を試そうとすると$ 12! = 479001600$通りとなり間に合わないが，公式の解説pdfのように並べ替え後に上からi行目になる行と下からi行目になる行のペアを作っていくことを考えると$ 11!! = 11 \times 9 \times 7 \times 5 \times 3 \times 1 = 10395$通りとなりなんとかなる．

なお，行数が奇数の場合はペアになれない行が1つできることになるが，後に掲載するソースコードではペアにならない行を最初に決めうちし，その行と全く同じ行を元のマス目に追加することで，その後の処理が行数の偶奇によって変化しないようにしている (ソースコード中の関数make_even)．

行のペアができたら，ちゃんと点対称になっているかチェックする．このチェックを行・列ごとの各文字の出現回数を数えるだけで済ませてしまうとテストケース100.txtにやられるので要注意．ここは行の交換が済んだマス目に対して，行ごとに「その行を上下に反転させたような行が存在するか？」を全てチェックしても144 (= 12×12) 通りしかないので間に合う．列数が奇数の場合はペアになる列が存在しない列が1つだけ存在することに注意．

ソースコード

ここには少ない関数で実装できた方の解法を掲載．

枝狩りで65ms→9msに高速化した方の解法はこちら．ただし枝狩り以外の部分の解法の流れは同じ．

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

string a[12];
int pairs[12];
int h, w;

bool check_columns();
bool make_even();
bool make_pair_of_lines(int);

bool check_columns(){
    string b[12];
    for(int i=0;i<h;i++){
        if(b[pairs[i]] == ""){
            b[pairs[i]] = a[i];
        }else{
            b[h-1-pairs[i]] = a[i];
        }
    }

    bool center = (w % 2 == 0);
    bool used[w];
    fill(used, used+w, false);

    for(int j=0;j<w;j++){
        if(used[j]) continue;
        used[j] = true;
        bool same = false;

        for(int jj=0;jj<w;jj++){
            if(used[jj]) continue;

            same = true;
            for(int i=0;i<h;i++){
                if(b[i][j] != b[h-1-i][jj]){
                    same = false;
                    break;
                }
            }
            if(same){
                used[jj] = true;
                break;
            }
        }

        if(!same){
            if(center) return false;
            else center = true;
        }
    }

    return true;
}

bool make_even(){
    h++;
    for(int i=0;i<h-1;i++){
        a[h-1] = a[i];
        pairs[h-1] = -1;
        if(make_pair_of_lines(0)) return true;
    }
    return false;
}

bool make_pair_of_lines(int paired_line){
    if(h % 2) return make_even();

    if(paired_line == h) return check_columns();

    int pair_line_first = -1;
    for(int i=0;i<h;i++){
        if(pairs[i] == -1){
            if(pair_line_first == -1){
                pair_line_first = i;
                pairs[pair_line_first] = paired_line/2;
                break;
            }
        }
    }

    for(int ii=0;ii<h;ii++){
        if(pairs[ii] == -1){
            pairs[ii] = paired_line/2;
            if(make_pair_of_lines(paired_line+2)) return true;
            pairs[ii] = -1;
        }
    }

    pairs[pair_line_first] = -1;

    return false;
}

int main(){
    cin >> h >> w;
    for(int i=0;i<h;i++) cin >> a[i];

    fill(pairs, pairs+h, -1);
    cout << (make_pair_of_lines(0)?"YES":"NO") << endl;
    return 0;
}

所感

実装重かったけどどちらかというとこういう問題の方が好きだし得意かも？

いや，この問題は実装以前に考察が難しいけど．

それから，何気にこの問題の解説で初めて二重階乗という概念を知った．

NoiminのNoise

AtCoder Regular Contest 095 E - Symmetric Grid

問題概要

解法概要

ソースコード

所感