はじめに
先月から開催されている、「競プロ典型90問」について、005 Restricted Digits（★7）に全く歯が立たず、答えを見てやっと理解しました。
そこで思ったのが、確かに答えを見れば「なるほど！」と思えるし、確かにその通りの実装もできるのですけれど、 私は一体これをどうやったら自力でひねり出せるようになるのか、と。私の現在のratingは1200付近なので、おそらくこの問題が次に出ても全く回答できる気がしません。
では、どのような思考の道順で考えていけばゴールにたどり着けるのか、つけないのか、整理してみようと思って書き始めたのがこれです。よって、上位の方には一瞬でわかることでも冗長に書いている点はご容赦ください。あくまでも、ratingが1200程度の人の頭の中の一例です。
まずは観察
ということで、最初に実際の数字を入れてみて観察します。$B$ の倍数になるものの個数を求めると言うことは、言い換えると $\bmod B$ で $0$ になるものの個数を求めればよいです。よって、$\bmod B$ の世界の中で考えればOK。
例：$B = 7, c = 1$
$1 = 10^0 ≡_7 1$
$10 = 10^1 ≡_7 3$
$100 = 10^2 ≡_7 2$
...
（$\bmod B$ を $≡_B$ で略記する。また、明らかな場合は $B$ も省略する。）
$c = \{1, 4, 9\}$ とすると、例えば
\begin{eqnarray*}
149 &=& 100 + 40 + 9 \\
&=& 1 \times 10^2 + 4 \times 10^1 + 2 \times 10^0 \\
&\equiv_7& 1 \times 2 + 4 \times 3 + 2 \\
&\equiv_7& 2
\end{eqnarray*}
\begin{eqnarray*}
449 &=& 400 + 40 + 9 \\
&=& 4 \times 10^2 + 4 \times 10^1 + 2 \times 10^0 \\
&≡& 4 \times 2 + 4 \times 3 + 2 \\
&≡& 1
\end{eqnarray*}
\begin{eqnarray*}
949 &=& 900 + 40 + 9 \\
&=& 2 \times 10^2 + 4 \times 10^1 + 2 \times 10^0 \\
&≡& 2 \times 2 + 4 \times 3 + 2 \\
&≡& 4
\end{eqnarray*}
下二桁を固定し、上一桁だけ替えてみたところ、$49$ の方は $0 \bmod B$ で変わらず、その値に上一桁の値を足した値が $\bmod B$ での三桁数の値になります。よって、$n$ 桁目までで $0,...,B-1$ のそれぞれになる組み合わせを求めておけば、あと一桁追加して $n+1$ 桁目までの組み合わせ数を求めることができます。
つまり、(1)「桁を増やしていくDPが使えそうだ」、と思いつきます。緑～水色だと、このくらいまでは思いつけそう。私もここまではいけました。
DP漸化式を書く
桁を増やしていくDPということは、桁に対して逐次更新していけば $N$ 桁にたどり着けそう。また、各桁について、$\bmod B$ でいくらになっているかを保存しなければならないので、$V[\bmod B の値]$ というベクトルを逐次更新していけばできそう。
そこで $D_n[x]$ を、「$\bmod B$ で $x$ になるような $n$ 桁の組み合わせの数」としてみる。$n$ を増やしていき、$D_N[0]$ を求めることができれば、これが本問題の解答になります。
まず一桁の場合。$D_1[x]$ は
\begin{eqnarray*}
1 &≡& 1 \rightarrow 10 = 1 \times 10 ≡ 1 \times 3 ≡ 3\\
4 &≡& 4 \rightarrow 40 = 4 \times 10 ≡ 4 \times 3 ≡ 5\\
9 &≡& 2 \rightarrow 90 = 9 \times 10 ≡ 2 \times 3 ≡ 6
\end{eqnarray*}
これと$1$ 桁目、つまり、$\{1,4,2\}$ とを和してできあがる値が $\bmod B$ でいくつになるかの組み合わせ数が $D_2[x]$ だから、$\{1,2,4\}$ と $\{3,5,6\}$ とをたしてみると
\begin{eqnarray*}
11 &=& 10 + 1 ≡ 3 + 1 ≡ 4 \\
14 &=& 10 + 4 ≡ 3 + 4 ≡ 0 \\
19 &=& 10 + 9 ≡ 3 + 2 ≡ 5 \\
41 &=& 40 + 1 ≡ 5 + 1 ≡ 6 \\
44 &=& 40 + 4 ≡ 5 + 4 ≡ 2 \\
49 &=& 40 + 9 ≡ 5 + 2 ≡ 0 \\
91 &=& 90 + 1 ≡ 6 + 1 ≡ 0 \\
94 &=& 90 + 4 ≡ 6 + 4 ≡ 3 \\
99 &=& 90 + 9 ≡ 6 + 2 ≡ 1
\end{eqnarray*}
よって、$D_2[x] = (3,1,1,1,1,1,1)$ となりました。
では、$D_3[x]$ はどうなるか。
$3$ 桁の組み合わせは、$2$ 桁の組み合わせ$\times 1$ 桁の組み合わせだから、$2$ 桁の数字の頭に $1$ つ数字を追加することを考える。つまり、$2$ 桁の数字に $c \times 100$ をたして、$\bmod B$ すると $3$ 桁の数字になるから、$\bmod B$ で $y$ である $2$ 桁の数字（個数は $D_2[y]$）は、$c \times 100$ をたすと、$c \times 100 + y \bmod B$ となります。
例（$B = 7, c = \{1,4,9\}$）ならば、$2$ 桁の組み合わせ $D_2[x]$ に対して $100, 400, 900$ をたせばよい。
\begin{eqnarray*}
100 &≡& 2\\
400 &≡& 1\\
900 &≡& 4
\end{eqnarray*}
これを、例えば $D_2[0]$ に入っている$3$ つの組み合わせ$14, 49, 91$ にたすと、
\begin{eqnarray*}
100 + (14, 49, 91) &≡& 2 + 0 ≡ 2 \\
400 + (14, 49, 91) &≡& 1 + 0 ≡ 1 \\
900 + (14, 49, 91) &≡& 4 + 0 ≡ 4
\end{eqnarray*}
また、他にも例えばたして $2$ になる組み合わせとしては、
\begin{eqnarray*}
400 + 99 &≡& 1 + 1 ≡ 2 \\
900 + 19 &≡& 4 + 5 ≡ 2
\end{eqnarray*}
があるので、$D_3[2]$ は先の $3$ つと合わせて $D_3[2] = 5$ となる。
つまり、$D_3[x]$ には、$c_k \times 100 + y ≡ x$ となる $(k,y)$ の組について、$D_2[y]$ をたしていけばよい。式で書くと、
\begin{equation*}
D_3[x] = \sum_{c_k \times 100 + y ≡ x} D_2[y]
\end{equation*}
これを $n$ について一般化すれば、
\begin{equation*}
D_{n+1}[x] = \sum_{c_k \times 10^n + y ≡ x} D_n[y]
\end{equation*}
なる漸化式を得られ、$n$ を $1$ ずつ増やしていけば答えにたどり着けます。
さて、この方法だと計算量は $\mathcal{O}(NKB)$になりまして、制約条件が★1の $N \le 10^5$ は超えられるのだけれど、★4の $N \le 10^{18}$ は超えられない。そもそも $N \le 10^{18}$ という制約は $\mathcal{O}(N)$だけでも超えられないので、必ず $\mathcal{O}(\log N)$ にするアルゴリズムがあるはず・・・つまり、桁数 $N$
を割り算で分割して小さい計算を行い、それらを組み上げて元の $N$ を構成する方法が必ずあるはず。
そういう目つきでさっきの式をもう一度眺めてみます。
\begin{equation*}
D_{n+1}[x] = \sum_{c_k \times 10^n + y ≡ x} D_n[y]
\end{equation*}
これは、一番上の桁に新しい数字を付加しているけれども、実は
\begin{equation*}
D_{n+1}[x] = \sum_{y \times 10 + c_k ≡ x} D_n[y]
\end{equation*}
でも同じになる。つまり、$n$ 桁の方を一段上に上げて、一番小さい桁に $c_k$ をくっつけても同じになる。計算済みのdpベクトルに対して、その上に $1$ 桁追加するのも、下に $1$ 桁追加するのも同じ、ということは逆に $1$ 桁に対して、(2)「$n$ 桁まとめて追加する」こともできるのでは？
10^18の壁を越える
この(2)を思いつくのは、私程度のランクのCoderには非常に厳しい気がするのですけれど、ひとまず思いついたとします。
すると、$1$ 桁というのは $D_1[z]$ でしたから、先ほどの式を次のように書き直すことができます。
\begin{equation*}
D_{n+1}[x] = \sum_{z \times 10^n + y ≡ x} D_1[z] \times D_n[y]
\end{equation*}
よく見るとこの式は $D_1$ 側と $D_n$ 側とが対等なので、$n$ 桁の数に対して上に $1$ 桁付加していると考えることもできるし、逆に $1$ 桁の数に対して下に $n$ 桁付加していると考えることもできる。実際、$n+1$ 桁の数があったときに、どちらを先に作ったとしても、場合の数は変わりません。
ということは、$n$ 桁の数に $m$ 桁を付加することもできるのではないか？と思って立式を試みると（下の方で $m$ の文字を使いたいので、ここでは $i,j$ に記号を替えて）、
\begin{equation*}
D_{i+j}[x] = \sum_{z \times 10^j + y ≡ x} D_i[z] \times D_j[y]
\end{equation*}
と書けることがわかります。$j$ 桁の数の上に $i$ 桁付加しているとも取れるし、$i$ 桁の数の下に $j$ 桁を付加しているとも取れますが、いずれにしても、任意の $i,j$ についてこの式が成立します。
さて、求めたいのは $D_N[x]$ であり、これを$\mathcal{O}(N)$ 程度の計算で求められればよかったのだから、 $N$ を $\log N$ 個程度の足し算で構成すればよい。最も単純なのは $N$ を二進数展開すること、つまり、$M = \lfloor\log_2(N) \rfloor$ として、$N$ を
\begin{equation*}
N = \sum_{m=0}^M n_m 2^m
\end{equation*}
（但し、$n_m$ は$0$ または $1$）と書き表すと、まず $D_{2^m}[x]$ を全部作っておいて（これは $\log_2 N$ 回程度で可能）、次にそれらを足し込んでいけば（これも $\log_2 N$ 回程度で可能）、$D_N[x]$ を作ることができます。計算量は、一回の遷移に $\mathcal{O}(B^2)$ かかるので、 全部で $\mathcal{O}(B^2 \log N)$ 程度になりそうです。
具体的には、まず $P_m[x] = D_{2^m}[x]$ としてこれを全て作成します。
\begin{eqnarray*}P_m[x]&=& D_{2^m}[x] \\
&=& D_{2^{m-1} + 2^{m-1}}[x] \\
&=& \sum_{z \times 10^{2^{m-1}} + y ≡ x} D_{2^{m-1}}[z] \times D_{2^{m-1}}[y] \\
&=& \sum_{z \times 10^{2^{m-1}} + y ≡ x} P_{m-1}[z] \times P_{m-1}[y]
\end{eqnarray*}
次に、$0 \le m$ について $V_m$ を $\sum_{l=0}^m n_l 2^l$ 桁目までの組み合わせ数とすれば、$V_{-1} = (1,0,...,0)$ として、$n_m = 1$ならば
\begin{equation*}
V_m[x] = \sum_{z \times 10^{2^m} + y ≡ b} V_{m-1}[z] \times P_m[y]
\end{equation*}
$n_m = 0$ ならば
\begin{equation*}
V_m[x] = V_{m-1}[x]
\end{equation*}
として、$m$ を増やしていけば、$\log_2 N + 1$ 回の更新で $V_M[x] = D_N[x]$ が得られます。特に $V_M[0]$ が解答になります。
おわりに
ということで、思いつきたかったのは、
(1)「桁を増やしていくDPが使えそうだ」
(2)「$n$ 桁まとめて追加する」
でした。式を見ながらこの二つに気づければ、005は攻略できたように思います。・・・ただ、実際には、自分では(2)は思いつけないだろうな・・・。
あと、美しい式を書くのが大事だなと思いました。おそらくrating上位の皆さんはそれが頭の中で瞬時に構成できているんだろうと思いますが、修行が足らないと、それを何らかの外部装置で補う必要があって、一つの有力な手段が、「きれいに式を描く」ということだなと。実際、
\begin{equation*}
D_{n+1}[x] = \sum_{c_k \times 10^n + y ≡ x} D_n[y]
\end{equation*}
では全然先が見えませんが、
\begin{equation*}
D_{n+1}[x] = \sum_{z \times 10^n + y ≡ x} D_1[z] \times D_n[y]
\end{equation*}
これが描けた段階で、かなり視界が開けるような気がします。（さらに、回答例でも注釈のあった、たたみ込みを高速計算する可能性も示唆されます。）もちろん、この記事は答えを見てから書いているので、自力でこれを導出できる気が全くしないのですけれど、ともかくその前に、美しい式を描くこと。描こうとすることが、rating積み増しを目指す上で大事だと思いました。
0 件のコメント:
コメントを投稿