Leading Zeros [第五回 アルゴリズム実技検定 D]

https://atcoder.jp/contests/past202012-open/tasks/past202012_d

解説

https://atcoder.jp/contests/past202012-open/submissions/22281196

特殊なソートが要求される問題。
C++ではソート関数を指定したソートを実装できる機能があるので、それを使ってソートを行った。
比較時に毎回文字列操作を行っていると遅いので、事前にできる文字列操作は実施したうえでソートを行う。
加えて、与えられる数値はint,longに収まらない可能性があるので、文字列で取って文字列で扱っていく必要がある。

事前準備

leading-zeroの個数を確認し、かつ、それを取り除いた文字列を作る。
例えば、0010という文字列であれば、

• 取り除いた文字列 -> 10
• leading-zeroの個数 -> 2個

をそれぞれ作っておく。
こうすることで比較するときに取り除いた文字列を使うことで、これまでの数が大きいか小さいかの比較が行える。
この比較で同じ値であった場合にleading-zeroの個数で比較をすることになるので、その個数もこの段階で取っておく。

特殊なソート関数

データ構造にはtupleによって3つの変数を1つにまとめた状態でソートする。
(leading-zeroを取り除いた文字列, leading-zeroの個数, 元々の文字列)
最後の元々の文字列は最終的な出力時に必要になるので付けている。
後で復元できるので必須ではない。

比較関数として、以下のようなものを書く

• leading-zeroを取り除いた文字列の大小を確認する
  • 文字列の長さが違う場合は長い方が大きい数なので、文字列長をまずは確認
  • 同じ文字列長ならstringで比較すれば、大小が一致するので問題ない
• 同じ値であれば、leading-zeroの個数を比較して多い方を小さくする

int N;
string S[101010];
using T = tuple<string, int, string>;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];

    vector<T> sorted;
    rep(i, 0, N) {
        string s = S[i];

        int leadingZero = 0;
        int len = S[i].length();
        rep(j, 0, len - 1) {
            if (S[i][j] == '0') leadingZero++;
            else break;
        }

        sorted.push_back({ S[i].substr(leadingZero), leadingZero, S[i] });
    }

    sort(all(sorted), [&](T a, T b) {
        if (get<0>(a).length() != get<0>(b).length()) return get<0>(a).length() < get<0>(b).length();
        if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
        return get<1>(a) > get<1>(b);
    });

    fore(t, sorted) printf("%s\n", get<2>(t).c_str());
}