I - Concat (maximize) Editorial
by 
kyopro_friends
Editorial for printing
- \(L=\max_i |S_i|\) とします。
- \(2\) つの文字列 \(A,B\) をこの順に連結した文字列を \(A+B\) と表すことにします。
- 数字のみからなる文字列 \(S\) を十進表記の整数と解釈した値を \(\mathrm{INT}(S)\) とします。
- \(S_i \succeq S_j\) を \(S_i+S_j\geq S_j+S_i\) と定めます。
後半パート
選ぶ \(K\) 個の文字列を決めたあとのことを考えます。
選ぶ \(K\) 個の文字列を決めたとき、「最大の整数を作ること」は「辞書順最大の文字列を作ること」と同値になります。
よって、次の問題が解ければ十分です。
問題： \(K\) 個の文字列が与えられる。これらを適切な順序で全て連結して作れる辞書順最大の文字列を求めよ。
これは次の方法で行えることが知られています。
- \(2\) つの文字列 \(S_i, S_j\) について、\(S_i\succeq S_j\) が成り立つとき、かつ、そのときに限り、\(S_i\) を \(S_j\) より前にする最適解が存在する。
証明
$S_i+S_j$ と $S_j+S_i$ は長さが等しいため、文字列としての大小関係と、整数として解釈したときの大小関係が一致します。$\mathrm{INT}(S_i+S_j)=\mathrm{INT}(S_i)\times 10^{|S_j|}+\mathrm{INT}(S_J)$ であることを用いると、$S_i+S_j \geq S_j+S_i$ は $\displaystyle \frac{\mathrm{INT}(S_i)}{10^{|S_i|}-1}\geq \frac{\mathrm{INT}(S_j)}{10^{|S_j|}-1}$ と同値になり、これは明らかに全順序を定めます。よって \(O(KL\log K)\) で解くことができます。
前半パート
選ぶ \(K\) 個の文字列の決め方を考えます。
\(S\) を \((|S_i|,\mathrm{INT}(S_i))\) という組をキーとして降順でソートし、indexを振り直します。選ぶべき \(K\) 個の文字列は次のどちらかになります。
- \(S_1,S_2,\dots,S_K\)
- \(S_1,S_2,\dots,S_{K-1}\) 及び、\(S_K,\dots,S_N\) のうち \(\mathrm{INT}(S_i)\) が最大のもの
証明
先頭に使う文字列 \(S_x\) を決めたとします。このとき残りの \(K-1\) 個で作れる文字列を \(T\) とすると \(\mathrm{INT}(S_x+T)=\mathrm{INT}(S_x)\times 10^{|T|}+\mathrm{INT}(T)\) (★)となるので、\(\mathrm{INT}(S_x)\neq 0\) ならば \(x\) に依らず \(T\) は \(|T|, \mathrm{INT}(T)\) の順で最大化するのが最適です。そのためには \(S\) のソート順の定義より indexの小さい順に取るのが最適です。
よって、\(x\leq K\) のとき、選ばれる \(K\) 個の文字列は \(S_1,\dots,S_K\) となります。\(x>K\) のとき、 \(x\) 以外に選ぶ \(K-1\) 個の文字列は\(x\) に依らず \(S_1,\dots,S_{K-1}\) であるため、(★)式より \(x\) は \(\mathrm{INT}(S_x)\) が最大のものを取るのが最適です。■
これらの \(2\) ケースはそれぞれ \(O(NL\log N )\) 時間で求められることから、この問題が解けました。
posted:
last update: