AtCoder ABC 042 B - 文字列大好きいろはちゃんイージー (4Q, 茶色, 200 点)

何気にちゃんと証明しようとすると、結構大変な問題な気もする！

• 問題へのリンク

問題概要

長さが である 個の文字列 が与えられる。

これらを好きな順番ですべて結合して得られる文字列のうち、辞書順最小のものを求めよ。

制約

• 

考えたこと

直感的には、 を辞書順で小さい順に並び替えて、その順に結合していけばよさそうである。

これは、実際正しい。ただし、それは文字列の長さがすべて等しいからである。

なお、この解法の計算量は となる。

文字列の長さが等しくないときの例外ケース

文字列の長さが等しくないときは例外がある。たとえば、2 個の文字列

"b", "ba"

を連結するとき、辞書順で小さい順に並び替えて結合すると

"b" + "ba" = "bba"

となる。しかし、実は "ba" を先にして、

"ba" + "b" = "bab"

とした方が、結合後の文字列の辞書順が小さくなる。

コード

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

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

    sort(S.begin(), S.end());
    string res = "";
    for (int i = 0; i < N; ++i) res += S[i];
    cout << res << endl;
}