ARC 084 D - Small Multiple

• 問題
• AC (FFT)
• AC (0-1 BFS)

問題: $0, 1, ..., 9$ のいずれかの整数からなる有限長の数列$(d_i)_{i \in \{0, 1, ..., m-1\}}$で、法$K$で

$10^0 \cdot d_0 + 10^1\cdot d_1 + ... + 10^{m-1} \cdot d_{m-1} = 0$

を満たすようなものについて、数列の総和 $d_0+d_1+...+d_{m-1}$の最小値を求めたい。

まず、各桁$d_i$は$0, 1, ..., ,9$の代わりに非負整数全体で考えてよい。というのも、ある桁が$10$以上である場合、それより桁和が小さい数列で同じ数を与えるものが必ず存在する（例: $10^0 \cdot 13 + 10^1 \cdot 1$ なら $10^0 \cdot 3 + 10^1 \cdot 2$）ので最小値は変わらないからである。

さて、$dp[l][x]$を次のように定める: $10^0, 10^1, 10^2, ...$から（重複を許して）$l$個選んで足し合わせて整数$x$を作ることが可能なら$dp[l][x]=1$、そのような選び方が存在しないなら$dp[l][x]=0$。このとき、$dp[l][0]=1$になるような最小の$l>0$が答えである。

$dp$の漸化式を与える。$l$個の和で作れる数は、$l-1$個の和で作れる数と$10^0, 10^1, 10^2, ...$のいずれかの和で作られるので、

$dp[l][x] = \bigvee_{i=0}^{x} \bigl(dp[l-1][x-i] \wedge dp[1][i] \bigr)$

と表すことができて、これは畳み込みの形になっている。ブール代数に特化した効率的な畳み込みアルゴリズムは見あたらなかったが、単純に$(+, \times)$でFFTしたあと、$1$以上の数をすべて$1$に訂正すればよい。なお、実際に計算するにあたっては、1次元の$dp$に対してin-placeに更新できる。

入力の制約より、答えは$9+9+9+9+9=45$を超えないので、高々43回畳み込みすればよいことになる。オーダーで表すと${\mathcal O}(K \log^2 K)$。

---

kyopro_friendsさんに教えていただいた解法だが、ちゃんと理解したと思えるのに時間がかかった。というか、ブール代数上の畳み込みが普通のFFTでできるというのがいまだに不思議だったりする。

https://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures
convolution theoremでググったら見つかったトピック。おもしろそう（難しそう）。

---

$dp$を

$dp[x] := \begin{cases} 1 & \qquad (\text{$x$が10の累乗}) \\ +\infty &\qquad (\text{それ以外}) \end{cases}$

と初期化して、畳み込み

$dp[x] := \min_{0 \le i \le x} (dp[x-i] + dp[i])$

を繰り返すのでもできそう？ $(\min, +)$の畳み込みはFFTほど効率的にはできないらしいけど、こう書き下すと最短経路問題であることはわかりやすくなる。つまり、$10^0, 10^1, 10^2, ...,$を足す操作を有向辺にしたとき、$dp[x]$は最終的に頂点$0$から頂点$x$への最短経路長になるので、BFSでも求まる。ただ、これだと想定のオーダーに達してはいない。¹ $+1$と$\times 10$だけで十分というのを自然に導きたいけど……

---

1. というか間に合っていない。計算量は${\mathcal O}(K^2)$で、$10$の位数が大きい場合が問題になる。間に合わない場合は（密グラフなので）どうせ3だろうと決め打てば一応通るけど…… ↩︎