ABC471 F - Concat (maximize)

考え方

まず、全ての文字列が数値的に $0$ である場合、答えは $0$ である。
このケースはいろいろなところで例外的な挙動を発生させる可能性があるので、別処理にしておく。
以下は、数値的に $0$ でないものが少なくとも $1$ つは存在している前提で考える。

では最初に、使う文字列群を完全に決めた後のことを考えよう。
この場合、どのような順で並べ替えても文字列の長さがかわらない。
したがって、辞書順最大のものが整数値としても最大となる。

さて、ではどう並べればよいかを考えよう。
$3$ つの文字列 $S_1,S_2,S_3$ があり、この順に並べるのが最善だったとする。
このとき、以下の $2$ つは明らかに成り立っている必要がある。

• $S_1+S_2$ と連結したものが、$S_2+S_1$ よりも辞書順で大きい、または同じものである
• $S_2+S_3$ と連結したものが、$S_3+S_2$ よりも辞書順で大きい、または同じものである

このとき、$S_1+S_3$ と $S_3+S_1$ は辞書順でどちらが大きいか？
答えは、$S_1+S_3$ と連結したものが、$S_3+S_1$ よりも辞書順で大きい、または同じものである。

以下、雑な証明。
特に、$S_1$ が文字列を意味するか数値を意味するかを厳密に記載していない。

$S_1+S_2$ と連結したものが、$S_2+S_1$ よりも辞書順で大きい、または同じものである。
これは、数でみると、$S_1\times 10^{|S_2|} + S_2 \geq S_2\times 10^{|S_1|}+S_1$ という意味である。
これを変形すると、これは $\dfrac{S_1}{10^{|S_1|}-1} \geq \dfrac{S_2}{10^{|S_2|}-1}$ となる。

$S_2+S_3$ と連結したものが、$S_3+S_2$ よりも辞書順で大きい、または同じものである。
これは同様に $\dfrac{S_2}{10^{|S_2|}-1} \geq \dfrac{S_3}{10^{|S_3|}-1}$ となる。

$2$ つの不等式から $\dfrac{S_1}{10^{|S_1|}-1} \geq \dfrac{S_3}{10^{|S_3|}-1}$ となる。
これは $S_1\times 10^{|S_3|} + S_3 \geq S_3\times 10^{|S_1|}+S_1$ と変形できる。
よって示された。

以上、証明終わり。

ということで、「$2$ つのどちらを前にした方が辞書順が後ろになるか」を基準に全体をソートすればよい。
これは、ラムダ式を用いるか、外部で比較関数を作って渡すか、自前でソートするか、いずれでもよい。

ここまでで、使う文字列群を完全に決めた後のことは解けた。
ここからは、その選び方を考える。

まずは、貪欲に長い方（タイブレークは辞書順が大きい方）を取ることを考えてみる。
この選び方は、多くの場合に解ける。
仮に、長い方 $K$ 個に含まれる $S_1$ の代わりに、含まれない $S_2$ を使ってできる文字列を作ったとしよう。
ほとんどの場合、$S_2$ 入りで作った列の $S_2$ がある位置に代わりに $S_1$ を入れる方が優秀だからである。
特に、$S_2$ が先頭以外にある場合は確定でよくなる。

ただし、上での言い方からわかるように、この貪欲が失敗する例外がある。
$S_2$ が先頭のものだった場合で、$S_1$ の先頭に $0$ がいくつか並んでいる場合だけ、そうとは限らない。
例えば、"010" "01" "2" という場合が失敗する例である。
貪欲にやると "01010" つまり $1010$ になるが、明らかに "2010" の方が優れている。

この場合、$S_2$ は先頭に来る $0$ ではない数値であることが明らか。
つまり、$S_2$ の候補は、長い方 $K$ 個に含まれないうち、最も数値として大きいもののみ考えればよい。

$S_1$ 側についても、もとの貪欲の成立根拠を考えれば、貪欲順位 $K$ 番目のもののみ考えればよい。
先頭にいるのは $S_2$ なので、$S_1$ が $K$ 位以外のものだった場合、$K$ 位を外してそこに $S_1$ を戻せばよい。

ということで、以下の $2$ つのいずれかが、必ず最善の文字列になっている。

• 上位から $K$ 個を採用する（パターン $1$）
• 上位から $K-1$ 個を採用し、残ったものから数値として最大のものを採用する（パターン $2$）

実際にどちらが最善になるかの判定は難しい。
そのため、両方の解を直接作って、長い方（タイブレークは辞書順が大きい方）を答えるのがよい。

このとき先頭の $0$ の削除は、先頭の文字列だけ行えばよい。
というのは、パターン $2$ は絶対に先頭が数値的に $0$ ではない数になっているため、この処理で問題ない。
パターン $1$ の方は先頭に数値的 $0$ がいる可能性があり、正しい文字列にならない可能性がある。
しかし、そうなったときは絶対にパターン $2$ に長さか辞書順で負けるため、答えに採用されることがない。

以上全てを実装すれば答えとなる。
計算量は $O(N\log N)$ である。

具体例での動作

次の入力を考える。

5 3
010
0012
9
90
12

まず、文字列を「長い方、同じ長さなら辞書順が大きい方」の順に見ると、

0012, 010, 90, 12, 9

となる。

上位から $K-1=2$ 個の 0012, 010 を採用する。
この $2$ 個を連結順でソートすると、

010, 0012

となる。

パターン $1$ では、次に長い 90 を採用する。
90 を連結順に挿入すると、

90, 010, 0012

となるので、

900100012

を得る。

パターン $2$ では、残っている

90, 12, 9

のうち数値として最大のものを選ぶ。
最大は 90 なので、この場合も

90, 010, 0012

となり、

900100012

を得る。

どちらのパターンでも同じ結果となるため、答えは 900100012 である。

010, 0012 の先頭の $0$ は、連結後には整数全体の先頭ではない。
そのため削除せず、そのまま残す。

注意点

各 $S_i$ は最大 $10$ 桁なので、数値として扱うと int 型からはみ出る場合がある。
long long 型を用いること。

答え全体は通常の整数型には収まらない。
文字列として扱うこと。

別解

特になし。