回文行列 [第三回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202005-open/tasks/past202005_f

解説

https://atcoder.jp/contests/past202005-open/submissions/14067015

たぶん、競技プログラミングをやってこないと回文を扱うプログラムを書いたことは無いだろうと思う。
まあそれはいいとして、回文ではabcdcbaのように鏡写しのような文字列になる。
鏡写しなので、先頭から1番目が決まれば、末尾から1番目が決まる。
2番目が決まれば、2番目が決まる。
加えて重要なのが、決まる組の間では同じである必要性があるが、決まる組と決まる組の間は独立に考えることができる。
よって、(先頭から1番目,末尾から1番目)の文字、(先頭から2番目,末尾から2番目)の文字、…を順番に確定させていこう。

先頭からi番目、末尾からi番目の文字をどうするかであるが、文字は26種類しかないので、
全ての文字について使用できるかを判定すればいい。
s1 := 先頭からi番目の文字列で使用されている文字の集合
s2 := 末尾からi番目の文字列で使用されている文字の集合
というのをあらかじめ作っておくと、ある文字が含まれるかを素早く判定できる。
含まれていれば採用する。

自分の実装では前半部分だけ答えを作って、後半部分は前半を反転させてくっつけている。

注意点として、Nが奇数の場合は真ん中の文字だけペアがないので、適当に先頭の文字列を使っている。

int N;
string S[505];
//---------------------------------------------------------------------------------------------------
string solve() {
    string pre = "";
    rep(i, 0, N / 2) {
        set<char> s1, s2;
        rep(x, 0, N) s1.insert(S[i][x]);
        rep(x, 0, N) s2.insert(S[N - 1 - i][x]);

        rep(_c, 0, 26) {
            char c('a' + _c);
            if (s1.count(c) && s2.count(c)) {
                pre += c;
                break;
            }
        }
    }

    if (pre.size() != N / 2) return "-1";

    string post = pre;
    reverse(all(post));

    if (N % 2 == 1) return pre + S[N / 2][0] + post;
    return pre + post;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    cout << solve() << endl;
}