Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 154 A問題 Swap Digit

AtCoder ARC154 ARC A問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 桁の整数 $A,B$ が与えられる.

以下の操作を好きな回数行うことができる.

$A,B$ の同じ桁にある数字同士を交換する.

操作後の $A \times B$ の最小値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$A,B$ は $N$ 桁の整数

解法

$A=B$ の場合は明らかである. 以降では $A \neq B$ とする.

また, $A \gt B$ としても一般性を失わない. また, $A,B$ の上から $i$ 桁目を $A_i, B_i$ と書くことにする.

$A \gt B$ であるから, $A_k \gt B_k$ となる整数 $k$ が存在する. また, これを満たす最小の $k$ を $K$ と書く. このとき, $i=1,2, \dots, (K-1)$ に対して, $A_i=B_i$ である. よって, 操作は上から $(K+1)$ 項目に制限してもよい. このとき, 操作後においても $A,B$ の大小関係は変化しない.

上から $i~(K+1 \leq i \leq N)$ 桁目を交換するとする. このとき, $d:=A_i-B_i$ とする. 操作前後における積の差は

$(A-d \times 10^{N-i})(B+d \times 10^{N-i})-AB=d \times 10^{N-i} (A-(B+d \times 10^{N-i}))$

である. 今, $A \geq B+d \times 10^{N-i}$ であるから, この値の正負は $d$ の正負と一致する. よって, $A$ 側に $A_i, B_i$ のうちの大きい方を, $B$ 側に $A_i, B_i$ の小さい方を割り当てると積が最小になることがわかる.

よって, 求めるべき答えは

$\displaystyle X:=\sum_{i=1}^N \max(A_i, B_i) 10^{N-i}, \quad Y:=\sum_{i=1}^N \min(A_i, B_i) 10^{N-i}$

として, $XY$ である. 計算量は $O(N)$ である.