Educational Codeforces Round 9 C. The Smallest String Concatenation

問題

codeforces.com

解法

勘で「a + b < b + a なら a, b の順番になるようにソートすれば良いんじゃね」と思って, 実際それで正しかったのですが, 理由がよくわからなかったので解説を見ました。

仮に p < q を満たす文字列 p, q について, q, p と並べたとすると, p+q < q+p より, これは明らかに損なので, p, q と並べるほうが良いです。これと上の定義で a < b かつ b < c であるならば, a < c となることを用いると, 単純に上の基準でソートすれば良いです。

で, 問題なのは 「a < b かつ b < c であるならば, a < c」が成り立つかどうかなんですが, a, b という文字列は 26 進数で書けることを考えると, a < b は a * 26^|b| + b < b * 26^|a| + a となります。(a は a を表す 26 進数の数, |a| は a という文字列の長さ)
これは a/(26^|a|-1) < b/(26^|b|-1) となり, a, b にのみ依存した数の比較で書けることがわかります。つまり, a < b かつ b < c なら a < c は明らかです。

bool cmp(const string& lhs, const string& rhs) {
    return lhs+rhs < rhs+lhs;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end(), cmp);
    string ans;
    for (string s : a) ans += s;
    cout << ans << endl;
    return 0;
}