Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
英小文字からなる N 個の文字列 S_1, \dots, S_N が与えられます.以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことを考えます.
- 英小文字 c を 1 つ選ぶ.全ての 1 \leq i\leq N について,S_i の末尾に c を追加する.
- 1 \leq i \leq N-1 を満たす整数 i を 1 つ選ぶ.S_i と S_{i+1} を入れ替える.
全ての操作の終了後に,辞書順で S_i \leq S_{i+1} が各 1 \leq i \leq N-1 について成り立つようにするとき,操作の合計回数の最小値を求めてください.
辞書順とは
文字列 S = S_1S_2\ldots S_{|S|} が文字列 T = T_1T_2\ldots T_{|T|} より辞書順で小さいとは,下記の 1. と 2. のどちらかが成り立つことを言います. ここで,|S|, |T| はそれぞれ S, T の長さを表します.
- |S| \lt |T| かつ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して,下記の 2 つがともに成り立つ.
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
- S_i が T_i よりアルファベット順で小さい文字である.
制約
- 入力される数値は全て整数
- 2 \le N \le 3 \times 10^5
- S_i は英小文字からなる文字列
- 1 \le |S_i|
- |S_1| + |S_2| + \dots + |S_N| \le 3 \times 10^5
入力
入力は以下の形式で標準入力から与えられる.
N S_1 S_2 \vdots S_N
出力
答えを 1 行に出力せよ.
入力例 1
5 ab rac a dab ra
出力例 1
3
操作の一例を示します.
- S_2 と S_3 を入れ替える.(S_1, \ldots, S_5) = (
ab
,a
,rac
,dab
,ra
) となる. - 各文字列の末尾に
z
を追加する.(S_1, \ldots, S_5) = (abz
,az
,racz
,dabz
,raz
) となる. - S_3 と S_4 を入れ替える.(S_1, \ldots, S_5) = (
abz
,az
,dabz
,racz
,raz
) となる.このとき全ての i = 1, \ldots, N-1 について S_i \leq S_{i+1} が満たされている.
3 回未満の操作により,全ての i = 1, \ldots, N-1 について S_i \leq S_{i+1} が満たされている状態にすることはできないので,3 を出力します.
入力例 2
3 kitekuma nok zkou
出力例 2
0
操作を行う前の時点で,全ての i = 1, \ldots, N-1 について S_i \leq S_{i+1} が満たされています.
入力例 3
31 arc arrc rc rac a rc aara ra caac cr carr rrra ac r ccr a c aa acc rar r c r a r rc a r rc cr c
出力例 3
175
i \neq j に対して S_i = S_j となりうることに注意してください.
Score: 1000 points
Problem Statement
You are given N strings S_1, \dots, S_N consisting of lowercase English letters. Consider performing the following two types of operations zero or more times in any order:
- Choose one lowercase letter c. Append c to the end of S_i for all 1 \leq i \leq N.
- Choose an integer i such that 1 \leq i \leq N-1. Swap S_i and S_{i+1}.
Find the minimum total number of operations required to make S_i \leq S_{i+1} in lexicographical order for all 1 \leq i \leq N-1.
What is lexicographical order?
A string S = S_1S_2\ldots S_{|S|} is said to be lexicographically smaller than a string T = T_1T_2\ldots T_{|T|} if 1. or 2. below holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
- The letter S_i comes before T_i in alphabetical order.
Constraints
- All input values are integers.
- 2 \le N \le 3 \times 10^5
- S_i is a string consisting of lowercase English letters.
- 1 \le |S_i|
- |S_1| + |S_2| + \dots + |S_N| \le 3 \times 10^5
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer in a single line.
Sample Input 1
5 ab rac a dab ra
Sample Output 1
3
Here is one way to operate.
- Swap S_2 and S_3. Now (S_1, \ldots, S_5) = (
ab
,a
,rac
,dab
,ra
). - Append
z
to the end of each string. Now (S_1, \ldots, S_5) = (abz
,az
,racz
,dabz
,raz
). - Swap S_3 and S_4. Now (S_1, \ldots, S_5) = (
abz
,az
,dabz
,racz
,raz
). At this point, we have S_i \leq S_{i+1} for all i = 1, \ldots, N-1.
It is impossible to make S_i \leq S_{i+1} for all i = 1, \ldots, N-1 with fewer than three operations, so you should print 3.
Sample Input 2
3 kitekuma nok zkou
Sample Output 2
0
Before any operation is performed, we have S_i \leq S_{i+1} for all i = 1, \ldots, N-1.
Sample Input 3
31 arc arrc rc rac a rc aara ra caac cr carr rrra ac r ccr a c aa acc rar r c r a r rc a r rc cr c
Sample Output 3
175
Note that we may have S_i = S_j for i \neq j.