はまやんはまやんはまやん

hamayanhamayan's blog

Neo-lexicographic Ordering [サイシードプログラミングコンテスト2021(AtCoder Beginner Contest 219) C]

https://atcoder.jp/contests/abc219/tasks/abc219_c

解説

https://atcoder.jp/contests/abc219/submissions/26483284

実装問題。
C++であれば、特殊なソートは、比較関数を独自に作ることで実装が可能である。

比較関数

2つの文字列が与えられたときに大小関係を判定するような比較関数を用意しよう。
通常であれば、charのまま大小比較すればそれがそのまま使えるのだが、今回は文字(文字コード)の順番と実際の順番が一致しないので、
文字を実際の順番に変換する必要がある。
自分はこれにはmapをつかって、mapping配列というのを用意した。
charを入れるとそれに対応した実際の順番が出てくるようになっている。
これを使って文字の先頭から大小比較をしていこう。

文字列のprefixがどちらも同じだった場合は文字数が少ない方が辞書順では早くなるので、
決まらなかったら文字数の昇順を条件として返してやればいい。

string X;
int N;
string S[50101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> N;
    rep(i, 0, N) cin >> S[i];
    map<char, int> mapping;
    rep(i, 0, 26) mapping[X[i]] = i;

    sort(S, S + N, [&](string a, string b) {
        int len = min(a.length(), b.length());

        rep(i, 0, len) {
            int x = mapping[a[i]];
            int y = mapping[b[i]];

            if (x != y) return x < y;
        }

        return a.length() < b.length();
    });

    rep(i, 0, N) printf("%s\n", S[i].c_str());
}