CF 632 C - The Smallest String Concatenation
問題
問題概要
個の文字列が与えられる。この個の文字列を全てを結合させることを考える。その中で辞書順最小となるものを求めよ。
- 文字は全て英小文字
- 文字列の長さの合計はを超えない。
アイデア
これは割と典型なテクらしい。文字列のvectorをソートする比較関数として、文字列に対してで評価するというものである。
これの正当性について考えてみる。まず、2種類の文字列について、この順序で並べるのが最適なものだとして、逆に並べて結合したものを考えてみると、が成り立つことから、の方が答えにふさわしいということになる。そして、この評価関数に推移性がある(かつならばが成り立つ)とすると、このように比較されるペアは隣り合っていて、それらをバブルソートのように交換していくことにより実現できると考えられる。
では本当に推移性はあるのか、というところでアルファベットは26種類の文字があるので、これを26進数と見なすならば、 はという数として表現でき、同様にはとなる。つまり評価関数はと言っていることと同様と見なすことが出来る。この式を変形して、というように単純な実数同士の比較に落としこむことが出来る。このような実数同士の比較に推移性があるのは明らか。以上よりこの解が正当性があるといえる。
実装(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; }