C - Digit Sum Minimization Editorial
by 
maspy
正の整数 \(n\) の各桁の和を \(S(n)\) と書くことにします。
◆ 各桁の和と繰り上がり
\(2\) つの整数 \(a,b\) を足すとき、もし繰り上がりが起こらなければ \(S(a+b) = S(a)+S(b)\) が成り立ちます。
繰り上がりとは、ある桁の \(10\) をひとつ上の桁の \(1\) に取り換える操作なので、この操作によって各桁の和は \(9\) 減少します。したがって、\(k\) 回の繰り上がりが起こるならば \(S(a+b) = S(a) + S(b) - 9k\) が成り立ちます。
本問題の目的は、繰り上がり回数の最大化と言い換えることができます。
◆ 最適解の構造
最適解について、次のことが分かります。
繰り上がり回数が \(1\) 以上であるような最適解が存在するならば、そのうちで \(1\) の位で繰り上がるものが存在する。
実際、そうでない最適解があるとき、初めて繰り上がる桁が \(1\) の位になるように巡回シフトしても、最適性が失われないことが確かめられます。
同様に、次を示すことができます：
繰り上がり回数が \(k\) 以上であるような最適解が存在するならば、そのうちで \(1, 10^1, \ldots, 10^{k-1}\) の位で繰り上がるものが存在する。
規則から外れている部分の巡回シフトを考えることで同様に証明できます。
結局、本問題を解くには次を解けばよいことが分かりました：
\(a\) の桁の並べ替え \((a_0,a_1,\ldots)\) および \(b\) の桁の並べ替え \((b_0,b_1,\ldots)\) であって、なるべく大きな \(K\) に対して次が成り立つものを求めよ。
- \(a_0 + b_0\geq 10\)
- \(a_i + b_i \geq 9\) （\(1\leq i < K\)）
ただし、\(i\) が \(a\) や \(b\) の桁数以上のときには \(a_i=0\) や \(b_i=0\) と見なす。
◆ 解法
\(a_0\) としては高々 \(9\) 通りの値しかないので、\(a_0\) を固定したときに解ければよいです。
\(a_0\) を固定すると、最適解は次の貪欲アルゴリズムにより構築することができます。
- \(a_0 + b_0\geq 10\) となる \(b_0\) を、可能なもののうちで最小のものとして選ぶ。
- 組 \((a_1,b_1), (a_2,b_2), \ldots\) を順に選んでいく。\(b_i\) は、\(a_i+b_i\geq 9\) となるようなものの中で最小のものを選ぶようにする。
◆ 解答例
posted:
last update: