すごくシンプルな面白い問題。

問題へのリンク

問題概要

$N$ 個の文字列 $S_{0}, S_{1}, \dots, S_{N-1}$ が与えられる。

これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。

制約

$1 \le N \le 5 \times 10^{4}$
$1 \le |S_{i}| \le 50$

解法

単純に $S_{0}, S_{1}, \dots, S_{N-1}$ を辞書順にソートして、小さい順に連結するのでは反例がある。

たとえば $S_{0}$ = "ab"、 $S_{1}$ = "abaab" のとき、

辞書順に並び替えると $S_{0}, S_{1}$ で、この順に連結すると "ababaab" になる
$S_{1}$ を先に連結すると、"abaabab" になる

後者の方が辞書順として小さい。

a + b < b + a で定義

そこで、 $N$ 個の文字列に対して、辞書順に代わる新たな順序を定義する。文字列 $a, b$ に対して

$a \lt\lt b$ 　 $\Leftrightarrow$ 　 $a + b \lt b + a$

と定義する。この順序は推移率を満たす。つまり、 $a \lt\lt b$ かつ $b \lt\lt c$ ならば、 $a \le\lt c$ が成り立つ。このことは英小文字からなる文字列を 26 進法の整数とみなすことで納得できる。

文字列 $a, b$ を表す整数を $f(a), f(b)$ とすると、次のようになる。

文字列 $a + b$ を表す整数は $10^{|b|} f(a) + f(b)$
文字列 $b + a$ を表す整数は $10^{|a|} f(b) + f(a)$

よって、 $a + b \lt b + a$ は

$10^{|b|} f(a) + f(b) \lt 10^{|a|} f(b) + f(a)$
$\Leftrightarrow \displaystyle \frac{f(a)}{10^{|a|}-1} \lt \frac{f(b)}{10^{|b|}-1}$

と同値になる。ゆえに、文字列 $a, b, c$ に対して、

$a \lt\lt b$ ならば、 $\Leftrightarrow \displaystyle \frac{f(a)}{10^{|a|}-1} \lt \frac{f(b)}{10^{|b|}-1}$
$b \le\lt c$ ならば、 $\Leftrightarrow \displaystyle \frac{f(b)}{10^{|b|}-1} \lt \frac{f(c)}{10^{|c|}-1}$

ということになり、 $\displaystyle \frac{f(a)}{10^{|a|}-1} \lt \frac{f(c)}{10^{|c|}-1}$ が成り立つ。つまり、 $a \lt\lt c$ が成り立つ。

推移率が成り立つので

推移率が成り立つので、上で定義した順序に従って、 $N$ 個の文字列 $S_{0}, S_{1}, \dots, S_{N}$ を並び替えることができる。結論から言えば、その順序に連結することで、連結後の文字列が辞書順最小となる。

以下のことを示そう。

$0, 1, \dots, N-1$ の順列 $p_{0}, p_{1}, \dots, p_{N-1}$ に対して、 $S_{p_{0}} + S_{p_{1}} + \dots + S_{p_{N-1}}$ をこの順に連結して辞書順最小であるための必要十分条件は、各 $i = 0, 1, \dots, N-1$ に対して

$S_{p_{i}} \lt\lt S_{p_{i+1}}$ 　( $\Leftrightarrow$ 　 $S_{p_{i}} + S_{p_{i+1}} \lt S_{p_{i+1}} + S_{p_{i}}$ )

が成り立つことである。

必要条件であることは明らか (満たさなければ改善できることが明らか) なので、十分条件であることが示せればよい。

簡単のため、 $S_{0} \lt\lt S_{1} \lt\lt \dots \lt\lt S_{N-1}$ のとき、任意の順列 $q_{0}, q_{1}, \dots, q_{N-1}$ に対して、 $S_{0} + S_{1} + \dots + S_{N-1} \lt S_{q_{0}} + S_{q_{1}} + \dots + S_{q_{N-1}}$ が成立することを言えばよい。

任意の順列が隣り合う要素を swap することで作れることから言える。ここではイメージを掴むために、具体例で見ていくことにする。一般の順列に対しても同様に示せる。

たとえば $N = 4$ として、 $S_{0} + S_{1} + S_{2} + S_{3} \lt S_{2} + S_{1} + S_{3} + S_{0}$ が成り立つことを示そう。

$S_{0} + S_{1} + S_{2} + S_{3}$
$\lt S_{0} + S_{2} + S_{1} + S_{3}$
$\lt S_{2} + S_{0} + S_{1} + S_{3}$
$\lt S_{2} + S_{1} + S_{0} + S_{3}$
$\lt S_{2} + S_{1} + S_{3} + S_{0}$

というように示せる。

コード

$N$ 個の文字列 $S_{0}, S_{1}, \dots, S_{N-1}$ を上述の順序に従って並び替えて、その順に連結すればよい。

計算量は $M = \max_{i} |S_{i}|$ として、 $O(MN\log N)$ と評価できる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];

    // S を並び替え
    auto cmp = [&](const string& a, const string& b) -> bool {
        return a + b < b + a;
    };
    sort(S.begin(), S.end(), cmp);

    // 連結
    string res = "";
    for (auto s : S) res += s;
    cout << res << endl;
}