公式

F - Concat (maximize) 解説 by en_translator

  • Let \(L=\max_i |S_i|\).
  • Denote the concatenation of two strings \(A\) and \(B\) by \(A+B\).
  • For a digit string \(S\), let \(\mathrm{INT}(S)\) be the integer represented by \(S\) in decimal.
  • Define \(S_i \succeq S_j\) as \(S_i+S_j\geq S_j+S_i\).

Latter part

Suppose we have determined which \(K\) strings to choose.

Once the choice is fixed, constructing the maximum integer is equivalent to constructing the lexicographically largest string.

This is because the number of digits (including leading zeros) in a constructable integer is fixed, and the ordering between integers with equal number of digits (allowing leading zeros) is same as the lexicographical ordering between strings.

Thus, it suffices to solve the following problem:

Problem: given \(K\) strings, find the lexicographically largest string obtained by arranging and concatenating them in any order.

It is known that the answer satisfies the following property:

  • There exists an optimal solution such that, for any two strings \(S_i\) and \(S_j\), \(S_i\) occurs prior to \(S_j\) if and only if \(S_i\succeq S_j\).
This is true because $\succeq$ defines a total order, and swapping adjacent elements violating this order does not worsen the answer.

Therefore, this part can be solved in \(O(KL\log K)\) time.

Former part

We will consider how to choose \(K\) strings.

Sort \(S\) in descending order by the keys \((|S_i|,\mathrm{INT}(S_i))\), and re-index them. Then the \(K\) strings to be chosen falls into one of the following:

  • \(S_1,S_2,\dots,S_K\)
  • \(S_1,S_2,\dots,S_{K-1}\), and the one among \(S_K,\dots,S_N\) with the maximum \(\mathrm{INT}(S_i)\)
Proof

Suppose that we have determined the string \(S_x\) that comes first. Then the string \(T\) obtainable by the remaining \((K-1)\) strings satisfies \(\mathrm{INT}(S_x+T)=\mathrm{INT}(S_x)\times 10^{|T|}+\mathrm{INT}(T)\) (★), so regardless of \(x\), it is optimal to take \(T\) that maximizes \(|T|\), then maximizes \(\mathrm{INT}(T)\). By definition of sorting order of \(S\), it is optimal to take those with smaller indices first.
Therefore, if \(x\leq K\), the \(K\) strings to be chosen are \(S_1,\dots,S_K\). If \(x>K\), the \((K-1)\) strings other than \(x\) must always be \(S_1,\dots,S_{K-1}\). By (★), it is optimal to choose \(x\) that maximizes \(\mathrm{INT}(S_x)\).■

These two cases can be inspected in \(O(NL\log N )\) time each, so the problem has been solved.

投稿日時:
最終更新: