ARC154 A Swap Digit 解説 - おれってどうしたらいいですか

解説が間違っているのではないかと思い、この記事を書くことにした。

問題文はこちら。

https://atcoder.jp/contests/arc154/tasks/arc154_a

ここで、 $a_ib_j + a_jb_i$ と $a_ib_i + a_jb_j$ のどちらが小さいかを考えます。これは、 $a_i,a_j$ の大小関係と $b_i,b_j$ の大小関係が一致しているのであれば前者、そうでないならば後者となります。

$�_{�}, �_{�大小関係が一致しているのであれば前者、そうでないならば後者となります。tete}$

解説に書かれているこの文自体は正しい。しかし $A\times B$ を小さくするために、ある桁で交換するかしないか決めたいならば $a_ib_j + a_jb_i$ (交換前)と $a_ia_j + b_ib_j$ ( $i,\space j$ どちらか一方の桁を交換後)のどちらが小さいかを考えることになるのではないか。これらの大小関係を調べる。

$(a_ib_j + a_jb_i) - (a_ia_j + b_ib_j) = a_i(b_j - a_j) + b_i(a_j - b_j) = (b_j - a_j)(a_i - b_i)$

以上より $b_j, \space a_j$ ペアと $b_i,\space a_i$ ペアの大小関係が一致しているとき $a_ib_j + a_jb_i$ 、そうでないとき $a_ia_j + b_ib_j$ の方が小さい(つまり $b_j, \space a_j$ ペアと $b_i,\space a_i$ ペアの大小関係が一致しているならば交換しない方がよい)。こうなると次が納得できる。

よって、 $�_{�}, �_{�}$ $a_i,\space b_i$ のうち小さい方を $a_i$ にし、大きい方を $b_i$ にすることによって $A\times B$ を最小化できます。

(小さい方を $b_i$ にし、大きい方を $a_i$ にすることによっても $A\times B$ を最小化できるはず)

また、解説放送その他で紹介されている以下のやり方の方が手っ取り早い気はする:ある桁を交換しても $A+B$ は保たれるから $A+B=C$ とする( $C$ は定数)。このとき

$A\times B = A(C-A) = -A^2+CA = -(A-\frac{C}{2})^2+\frac{C^2}{4}$ ということで、 $A$ は $C/2$ (すなわち $A,\space B$ の平均)より離れているほど $A\times B$ は小さくなる(このことから逆に積を大きくしたいなら $A,\space B$ が同じ大きさになるように寄せるとよいことがわかる)。

これを書いた動機

解説が理解できなくて数日間悩んでから、解説のある個所を変更することで納得のいく文章になったので、その箇所は書き間違いではないかと思った。適当にインターネットで検索した限りだと解説に言及している人や上で書いたようなことを言っている人が見つからなかった。友人(1人)に、具体的な個所は伏せて、間違いがあると思っているが君はどう思うかと伝えたうえで見てもらったところ彼も自分と同じ考えに至った。それで自分だけの勘違いでもなさそうだと思いここに書くことにした。もともと解説が正しく自分が理解できていない、すでに指摘している人がいる、上で自分が書いてることに間違いがあるなど、なんでもあれば知らせていただきたい。