https://atcoder.jp/contests/abc225/tasks/abc225_f

题目大意

有 \(N\) 张卡片。第 \(i\) 张卡片上写了一个字符串 \(S_i\)。今要从中选择 \(K\) 张卡片，把上面的字符串以任意顺序拼接。试求所能得到的字典序最小的字符串。

Constraints

• \(1 \le K \le N \le 50\)
• \(1 \le |S_i| \le 50\)
• \(S_i\) 由小写英文字母构成。

解说

用符号 \(\oplus\) 表示字符串的拼接运算。

取定 \(K\) 个字符串。设 \(S_{i_1}, \dots, S_{i_K}\) 是这 \(K\) 个字符串的字典序最小的拼接方案。这个拼接方案需要满足的必要条件是，交换任意两个相邻的字符串，整个字符串的字典序不会变小。换言之，对每个 \(1 \le j \le K - 1\) 有 \(S_{i_j} \oplus S_{i_{j + 1}} \le S_{i_{j + 1}} \oplus S_{i_{j}}\)。

设 \(a, b\) 是两个非空的由小写英文字母构成的字符串。现在我们来考察 \(a \oplus b < b \oplus a\) 这个二元关系，把这个二元关系记作 \(a \prec b\)。首先注意到，若 \(a, b\) 长度相等，则 \(a < b\) 当且仅当 \(\Bar a < \Bar b\)。\(\Bar a\) 表示 \(a\) 所表示的 26 进制整数。因此 \[\begin{split} a \oplus b < b \oplus a \iff \Bar{a \oplus b} < \Bar{b \oplus a} \end{split}\] 注意，上式左边的 \(<\) 表示字符串的字典序，右边的 \(<\) 是比较整数的大小。把上式右边改写为 \[\begin{split} \Bar{a} \times 26^{|b|} + \Bar{b} < \Bar{b} \times 26^{|a|} + \Bar{a} \iff \Bar{a} \times (26^{|b|} - 1) < \Bar{b} \times (26^{|a|} - 1) \\ \iff {\Bar a \over 26^{|a|} - 1} < {\Bar b \over 26^{|b|} - 1} \end{split}\]

可见

• \(\prec\) 是非空字符串集合上的一个 strict weak ordering。
• \(\prec\) 所导出的等价类在 \(\oplus\) 运算下封闭。
• 字典序最小的拼接方案一定符合这个 strict weak ordering。

分析至此，我们就得到一个解法：把输入的 \(N\) 个字符串按 \(a \prec b\) 排序，逆着 \(\prec\) 的顺序进行类似01背包的DP。注意：不能顺着 \(\prec\) 的顺序进行状态转移。因为，任取字符串 \(a\)， \(x \mapsto a \oplus x\) 是保序映射，而 \(x \mapsto x \oplus a\) 不保序。例子：\(\texttt{a} < \texttt{aa}\) 而 \(\texttt{ab} > \texttt{aab}\)。

注

这篇题解是根据官方题解写的。我想说明“如何想到这个解法？”。在理解官方题解的过程中，我认识到 strict weak ordering 和保序映射这两个概念。