Educational Codeforces Round 9 C. The Smallest String Concatenation (R1700)

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

• 問題へのリンク

問題概要

個の文字列 が与えられる。

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

制約

• 
• 

解法

単純に を辞書順にソートして、小さい順に連結するのでは反例がある。

たとえば = "ab"、 = "abaab" のとき、

• 辞書順に並び替えると で、この順に連結すると "ababaab" になる
• を先に連結すると、"abaabab" になる

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

a + b < b + a で定義

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

　　

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

文字列 を表す整数を とすると、次のようになる。

• 文字列 を表す整数は
• 文字列 を表す整数は

よって、 は

と同値になる。ゆえに、文字列 に対して、

• ならば、
• ならば、

ということになり、 が成り立つ。つまり、 が成り立つ。

推移率が成り立つので

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

以下のことを示そう。

---

の順列 に対して、 をこの順に連結して辞書順最小であるための必要十分条件は、各 に対して

　(　)

が成り立つことである。

---

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

簡単のため、 のとき、任意の順列 に対して、 が成立することを言えばよい。

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

たとえば として、 が成り立つことを示そう。

というように示せる。

コード

個の文字列 を上述の順序に従って並び替えて、その順に連結すればよい。

計算量は として、 と評価できる。

#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;
}