題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟣 ABC434F Concat (2nd)

Problem Statement

題目簡述

給定 NN 個由小寫英文字母組成的字串 S1,S2,…,SNS_1, S_2, \dots, S_N。
對於所有長度為 NN 的排列 P=(P1,P2,…,PN)P = (P_1, P_2, \dots, P_N)，我們依序將 SP1,SP2,…,SPNS_{P_1}, S_{P_2}, \dots, S_{P_N} 拼接在一起，形成一個新字串。
共有 N!N! 種可能的排列，這會生成 N!N! 個字串。將這些字串按字典序從小到大排序，形成序列 A1,A2,…,AN!A_1, A_2, \dots, A_{N!}。
請輸出字典序第二小的字串 A2A_2。

每組輸入包含 TT 個測試筆數。

Constraints

約束條件

  • 1≤T≤1.5×1051 \le T \le 1.5 \times 10^5
  • 2≤N≤3×1052 \le N \le 3 \times 10^5
  • SiS_i 是由小寫英文字母組成的字串，且 1≤∣Si∣≤106−11 \le |S_i| \le 10^6 - 1。
  • 在同一組測試中，所有測試筆數的 NN 之和不超過 3×1053 \times 10^5。
  • 在同一組測試中，所有測試筆數的 ∣Si∣|S_i| 之和不超過 10610^6。

思路：第二小的貪心交換

先把「如何排出第一小」當成已知前提：若兩個字串 X,YX, Y 滿足 X+Y<Y+XX + Y < Y + X，就讓 XX 排在 YY 前面。依照這個規則排序後，得到的序列記為 AA，直接拼接就是字典序最小的字串。

真正需要處理的是：在這個最小排列之外，哪一個不同排列會產生第二小的拼接結果？

等價交換：最小字串可能同時也是第二小

如果排序後存在相鄰兩個字串滿足

Ai+Ai+1=Ai+1+AiA_i + A_{i+1} = A_{i+1} + A_i

那麼交換它們不會改變拼接結果，卻會得到另一個不同排列。因此排列序列中的第一名與第二名對應到同一個字串，答案就是最小字串本身。

Example

ab 與 abab 就是典型例子：

1
2
ab + abab = ababab
abab + ab = ababab

兩個排列不同，但拼接結果完全相同。

接下來只需要討論沒有等價相鄰對的情況。此時每一組相鄰元素都嚴格滿足

Ai+Ai+1<Ai+1+AiA_i + A_{i+1} < A_{i+1} + A_i

候選只會來自一次相鄰交換

若某個排列相對於最小排列有至少兩個逆序對，就可以先修正其中一個逆序對，得到一個仍然不同於最小排列、但字典序更小的排列。換句話說，這種排列前面至少已經有「最小排列」與「修正一個逆序後的排列」，所以不可能是第二小。

因此第二小只可能來自恰好一次相鄰交換。令 TiT_i 表示交換排序後第 ii 個與第 i+1i+1 個字串後得到的拼接結果。

在所有 TiT_i 裡，多數位置其實可以直接淘汰：若交換位置太前面，它會比「交換最後兩個」更早破壞最小前綴，而且破壞處一定比較大。

證明：為何只剩最後兩種候選？

先比較 TiT_i 與 TN−1T_{N-1}，其中 i≤N−3i \le N-3。

兩者共享前綴 A1A2…Ai−1A_1 A_2 \dots A_{i-1}。接著：

  • TiT_i 會接上 Ai+1AiA_{i+1} A_i，因為它在這裡交換。
  • TN−1T_{N-1} 仍接上 AiAi+1A_i A_{i+1}，因為它只交換最後兩個。

由於目前沒有等價相鄰對，必有

AiAi+1<Ai+1AiA_i A_{i+1} < A_{i+1} A_i

且這兩段長度相同，都是 ∣Ai∣+∣Ai+1∣|A_i| + |A_{i+1}|。所以在第一次不同的字元處，TN−1T_{N-1} 的字元一定更小；後面接什麼都無法扭轉這個結果。

因此所有 i≤N−3i \le N-3 的交換都會被 TN−1T_{N-1} 淘汰。

唯一不能直接淘汰的是 TN−2T_{N-2}。它與 TN−1T_{N-1} 的分歧位置不同，不是在同一組對齊區塊上比較，所以必須保留下來實際比較。

所以當 N>2N > 2 且不存在等價相鄰對時，答案只需要在兩個候選中取較小者：

  • 候選 1：交換最後兩個
    A1A2…AN−2ANAN−1A_1 A_2 \dots A_{N-2} A_N A_{N-1}
  • 候選 2：交換倒數第三與倒數第二個
    A1A2…AN−3AN−1AN−2ANA_1 A_2 \dots A_{N-3} A_{N-1} A_{N-2} A_N

若 N=2N = 2，兩個排列就是第一小與第二小，因此直接交換兩個字串輸出即可。

Example

假設排序後的序列是 ["a", "aab", "b"]。

  • 交換最後兩個："a" + "b" + "aab" = "abaab"
  • 交換前兩個："aab" + "a" + "b" = "aabab"

雖然交換前兩個比較早破壞前綴，但整體字典序反而更小，因此倒數兩種候選都要實際比較。

排序瓶頸

這題的主要瓶頸不在後面的候選比較，而在排序。比較兩個字串時會用到 X+YX + Y 與 Y+XY + X，單次比較可能掃過 O(∣X∣+∣Y∣)\mathcal{O}(|X| + |Y|) 個字元；若排序過程反覆比較同一批長字串，就可能超時。

Python 的 sort() 使用 Timsort，可以搭配這個比較方式通過，但注意使用 PyPy 時，若使用 cmp_to_key 仍然會 TLE，必須使用繼承自 str 的自定義類別並覆寫 __lt__ 方法；C++ 若使用 std::sort，則需要注意針對性測資造成的退化風險，但可以透過 random_shuffle 來避免。關於詳細的複雜度分析請參考：

參考資料

複雜度分析

  • 時間複雜度：O(∑∣Si∣log⁡2N)\mathcal{O}(\sum |S_i| \log^2 N)
    • 排序是主導項；後續檢查等價相鄰對、構造並比較兩個候選都是線性時間。
  • 空間複雜度：O(∑∣Si∣+N)\mathcal{O}(\sum |S_i| + N)
    • 主要用於儲存字串序列，以及拼接候選時產生的暫存字串。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from itertools import pairwise
from functools import cmp_to_key


class C(str):
    def __lt__(self, other):
        return self + other < other + self


def solve():
    N = int(input())
    words = [input() for _ in range(N)]

    def cmp(x, y):
        xy = x + y
        yx = y + x
        return (xy > yx) - (xy < yx)

    # words.sort(key=cmp_to_key(cmp))  # CPython AC, PyPy TLE
    words.sort(key=C)  # CPython/PyPy AC

    if N == 2:
        words[-1], words[-2] = words[-2], words[-1]
        print("".join(words))
        return

    for w1, w2 in pairwise(words):
        if w1 + w2 == w2 + w1:  # e.g. ab + abab = abab + ab
            print("".join(words))
            return

    words[-1], words[-2] = words[-2], words[-1]
    ans1 = "".join(words)
    words[-1], words[-2] = words[-2], words[-1]
    words[-2], words[-3] = words[-3], words[-2]
    ans2 = "".join(words)
    print(min(ans1, ans2))


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

Cover Image Credit

The cover image was created by @floomf. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.