読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

CF 632 C - The Smallest String Concatenation

programming Codeforces

問題

Problem - 632C - Codeforces

問題概要

n個の文字列a_iが与えられる。このn個の文字列を全てを結合させることを考える。その中で辞書順最小となるものを求めよ。

  •  1 \le n \le 5*10^4
  •  1 \le |a_i| \le 50
  • 文字は全て英小文字
  • 文字列の長さの合計は5*10^4を超えない。

イデア

これは割と典型なテクらしい。文字列のvectorをソートする比較関数として、文字列a,bに対して a+b \lt b+aで評価するというものである。

これの正当性について考えてみる。まず、2種類の文字列x,yについて、この順序で並べるのが最適なものだとして、逆に並べて結合したもの y+xを考えてみると、 x+y \lt y+xが成り立つことから、x+yの方が答えにふさわしいということになる。そして、この評価関数に推移性がある( a \lt bかつ b \lt cならば a \lt cが成り立つ)とすると、このように比較されるペアは隣り合っていて、それらをバブルソートのように交換していくことにより実現できると考えられる。

では本当に推移性はあるのか、というところでアルファベットは26種類の文字があるので、これを26進数と見なすならば、 a+ba * {26}^{|b|} + bという数として表現でき、同様にb+ab * {26}^{|a|}+aとなる。つまり評価関数 a+b \lt b+a a * {26}^{|b|} + b \lt b * {26}^{|a|}+aと言っていることと同様と見なすことが出来る。この式を変形して、\displaystyle \frac{a}{{26}{|a|}-1} \lt \frac{b}{{26}^{|b|}-1}というように単純な実数同士の比較に落としこむことが出来る。このような実数同士の比較に推移性があるのは明らか。以上よりこの解が正当性があるといえる。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp(x,y) make_pair((x),(y))
#define pb(x) push_back(x)
#define fi first
#define se second

inline bool cmp(const string& a, const string& b)
{
    return a+b < b+a;
}

int main()
{
    int n;
    cin >>n;
    vector<string> a(n);
    rep(i,n) cin >>a[i];

    sort(all(a),cmp);
    rep(i,n) cout <<a[i];
    cout <<endl;
}