AtCoder Regular Contest 154 A問題 Swap Digit
問題
提出解答
問題の概要
桁の整数
が与えられる.
以下の操作を好きな回数行うことができる.
の同じ桁にある数字同士を交換する.
操作後の の最小値を求めよ.
制約
は
桁の整数
解法
の場合は明らかである. 以降では
とする.
また, としても一般性を失わない. また,
の上から
桁目を
と書くことにする.
であるから,
となる整数
が存在する. また, これを満たす最小の
を
と書く. このとき,
に対して,
である. よって, 操作は上から
項目に制限してもよい. このとき, 操作後においても
の大小関係は変化しない.
上から 桁目を交換するとする. このとき,
とする. 操作前後における積の差は
である. 今, であるから, この値の正負は
の正負と一致する. よって,
側に
のうちの大きい方を,
側に
の小さい方を割り当てると積が最小になることがわかる.
よって, 求めるべき答えは
として, である. 計算量は
である.