問題
正整数 $n$ が与えられる。$1$ や $11$、$111$ などの $1$ のみからなる数の加減算によって $n$ を作る (例: $24=11+11+1+1, 102=111-11+1+1$)。式中に現れる $1$ の個数の最小値を求めよ。
解法
$\displaystyle \underbrace {11 \cdots 1} _ { \text { $k$ 個 } } = \dfrac {10 ^ k - 1 } { 9 }$ を使う個数を $a_k$ とおく。ただし、正の数として使う場合は $+1$ 個、負の数として使う場合は $-1$ 個としてカウントする。このとき、求めるべき値は次のように表される。
$$\min\left\{\sum _ { k = 1 } ^ { \infty } k \cdot | a _ k | \;\middle|\; \sum _ { k = 1 } ^ { \infty } (10 ^ k - 1) a _ k = 9 n\right\}$$
$\displaystyle S\coloneqq \sum _ { k = 1 } ^ \infty a_k$ を固定したときの答えを $A _ S$ とおくと、
$$A_S = \min\left\{\sum _ { k = 1 } ^ { \infty } k \cdot | a _ k | \;\middle|\; \sum _ { k = 1 } ^ { \infty } 10 ^ k \cdot a _ k = 9 n + S\land \sum _ { k = 1 } ^ \infty a_k = S \right\}$$
であり、求める値は $\min_S A_S$ である。
$a_k\neq 0$ となる最大の $k$ は $\lceil \log _ {10} |9n+S| \rceil + 1$ 以下としてよく、また、$| a _ k | \lt 10$ の場合のみを考えても十分なので $S$ は $|S| \leq 9 \cdot (\lceil\log _ {10} |9n+S| \rceil + 1)$ を満たす範囲を調べれば十分である。
$A_S$ は桁 DP で (上から何桁決めたか ($=i$)、上から $i$ 桁だけ見たときの目標との差分、上から $i$ 桁の $a_k$ の和) を持てば求めることができる。差分は高々 1 としてよいので、DP テーブルの大きさは $O( ( \log n) ^ 2 )$、遷移は $O(1)$ となる。
桁 DP を $O(\log n)$ 回行うので、全体の計算量は $O((\log n) ^ 3)$ となる。ただし、様々な部分に定数倍として $10$ や $20$ といった大きな係数が付くので注意。
感想
制約が本当は $10 ^ {50}$ なのを $2 ^ {50}$ と読み違えて long long を使ってて永遠に合わなかったのが悲しい...
$S$ を固定して解いた方が頭が壊れないと思って分離したけど、$S$ を固定せずに DP をして適切に枝刈りをすれば $O((\log n) ^ 2 \log \log n)$ とかになると思います (map でサボってますが、こんなイメージです: 提出)。
