AtCoderログ：0057 - ABC 042 B

問題

問題文

いろはちゃんは 長さ $L$ の文字列を $N$ 個持っており、それぞれ $S_1,S_2,\ldots,S_N$ です。
それらの文字列を好きな順番で全て結合してできる文字列のうち、もっとも辞書順で小さいものを求めてください。
なお、ある文字列 $s=s_1s_2s_3\ldots s_n$ と $t=t_1t_2t_3 \ldots t_m$ について、以下のどちらかを満たすとき、辞書順比較で $s<t$ であるといいます。
・ある整数 $i~(1 \le i \le {\rm min}(n,m))$ に関して、$1 \le j <
i$ を満たす任意の整数 $j$ において $s_j=t_j$ が成立し、かつ $s_i < t_i$ が成立する。
・任意の整数 $i~(1 \le i \le {\rm min}(n,m))$ に関して $s_i=t_i$ が成立し、かつ $n<m$ が成立する。

制約

・$1 \le N, L \le 100$
・全ての $i~(1 \le i \le N)$ に対し、$S_i$ の長さは $L$ に等しい。
・各 $i$ について, $S_i$ は全て半角英小文字のみから成る文字列である。

収録されている問題セット

• AtCoder に登録したら次にやること (第06問類題)

回答

回答1 (AC)

結合した文字列が辞書順で最も小さくなるのは、$N$ 個の文字列を小さい順に並べたときです。処理としては、それぞれの文字列を配列 s() に受け取った後、小さい順 (昇順) にソートし、小さい順に出力すれば良いでしょう。コードは以下のようになりました。

abc042b-1.cpp

#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.at(i);
  }

  sort( s.begin(), s.end() );

  for ( int i=0; i<n; i++ ) {
    cout << s.at(i);
  }
}

調べたこと

AtCoder の解説 → 公式解説

回答と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0056 - 問題セットのまとめ