想定解法

各桁を並び替えて、その並び替えた数列のどこかに１つ区切りを挿入することを考える。各桁の並び替えの全探索と区切りの入れ方から計算量はO((L-1)L!)。(Lは桁数)

別解

空の文字列A,Bに各桁の数字をどちらに、どのような順番で入れれば、A*Bが最大になるかを考える。まず、A,Bどちらかに数字を入れるときは数字のでかいものから入れるほうが良いということがわかる。そのため、各桁での数字を降順でソートしておく。次に各イテレーションでA,Bどちらにpushするのが最適かを考える必要があるが、結論から言うとこれは現時点でのA,Bを比較したときに値が小さい方にpushする方が良い。下の例のように処理を行う。赤下線がpushした数字で直前のA,B間の大小関係でどちらにpushするかを決めている。
<証明>
A,B($A \geqq B$)とpushする数字Xがある。
Aにpushした場合: $$ (10A + X)\times B=10AB+BX $$ Bにpushした場合: $$ (10B+X)\times A=10AB+AX $$

$A \geqq B$より、Bにpushした方が次の$A\times B$の値が大きくなる。終

また、Nに0が含まれている場合は、その0を取り除いておき、後でpow(10,zero_count)を掛けてやれば良い。この方法における計算量は、ソートがボトルネックとなっているため、O(L*log(L))
提出：

考えたこと

• 0があることに関しては、0である桁数さえ持っていれば取り除いてしまって良い。（一番末尾に0が来たほうが最適であることと、出力するものが掛け算であるために、A,Bどちらへの挿入でも結果は変わらないことから）
• 各桁を降順ソートすること。(大きい数字をa,bの大きい位に入れていくため)
• 「A,Bに大きい順で数字を交互に入れていけばいい？」と雑に考えたが、WA。反例は98321。9をA,8をBに入れた後、もう一度Bに8を入れる必要がある。