AtCoder Beginner Contest 221 C問題 Select Mul
問題
提出解答
問題の概要
整数 の各桁の数字を2つの正の整数に分割し, 並び替えることによって, 2つの正の整数
を作る. このとき,
を最大化せよ. ただし,
において, leading-zero は認められない.
制約
には
でない桁が2つ以上含まれる.
解法
まず, グルーピングを全探索する. このとき, とはなり得ないことから,
の桁数を
とすると,
である.
このとき, 2つのグループをグループ A,B とすると, グループに分け方は 通りである.
各グループに分けられた数字をうまく並び替えて積を最大化するにはどうすればよいだろうか? まず, それぞれをグループの中で最大化する. では, グルーピングの中で,
を最大化するためにはどうすればよいか. 結論からいうと, 各桁の数字が大きい順になるように並び替えれば
を最大化できる.
このように各グルーピングにおいて数字を大きい順にならべた整数の積を全探索することによって正解を導くことができる.
なお, leading-zero はこの問題においては特別な考慮をしなくてもうまいこと処理してくれる.
