AtCoder Beginner Contest 135 D - Digits Parade

お題箱より。

D - Digits Parade

「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」という、是非とも押さえておきたい問題パターンの入門としてぴったりです。いつも以上に丁寧めに書きたいと思います。

解法

「前から○文字」を順に見ていく

まずは作れる数を全列挙してみましょう。文字列 $S$ として 51?3 を考えてみます。

このくらいなら作れる数は見ただけで10通り列挙できそうですが…今回はあえて、「前から○文字だけを見た時に作れる数」を最初から順番に見ていくようにします。

f:id:betrue12:20190821233909p:plain

前から1文字：1文字目が 5 なので、作れる数は $\lbrace 5 \rbrace$ 。
前から2文字：2文字目が 1 なので、先ほどの $\lbrace 5 \rbrace$ の要素の末尾に 1 をくっつけて、作れる数は $\lbrace 51 \rbrace$ 。
前から3文字：3文字目が ? なので、これは 0 から 9 まで10通りのパターンがある。先ほどの $\lbrace 51 \rbrace$ の末尾に 0 から 9 を付けたものをそれぞれ考えて、作れる数は $\lbrace 510, 511, ..., 519 \rbrace$ 。
前から4文字：4文字目が 3 なので、先ほどの $\lbrace 510, 511, ..., 519 \rbrace$ それぞれの末尾に 3 をくっつけて、作れる数は $\lbrace 5103, 5113, ..., 5193 \rbrace$ 。

ちょっと省略表記していますが、10通りの数を列挙しました。この10個のうち13で割って5で余る数の個数が答えです。

あえて順番に見ていったのは、この

「前から○文字」の時点で作れる数を、少ない文字数から順番に列挙していく。
「前から文字」で作れる数は、「前から文字」で作れる数それぞれの末尾に、の文字目の数を付け足すことで作ることができる。
- このとき $i+1$ 文字目が ? だったら、作れる数の個数が10倍になる。

という考え方がとても大事だからです。

このように作れる数を列挙していって、最後に全部の数を13で割ってみれば、いつかは答えを求めることができます。しかし例えば文字列が ????????.... のようなものだった場合、1文字見るたびに個数が10倍になってものすごい個数になってしまいます。

そこで威力を発揮するのが「状態をまとめる」ということ。「以降ずっと同じ扱いをしていいような数はまとめてしまい、そのまとめた個数だけを覚えておく」という考え方です。

同じ扱いをしていい数を「まとめる」

この問題では、いくら大きな数を作っても最後には13で割った余りしか使いません。どれだけ多くの数を列挙しても、13で割った余りによってたった13通りに分類されてしまうのです。であれば、列挙している途中でどんどん分類して、まとめてしまうことはできないでしょうか？

先ほどの「ある数の末尾に数字を1個付け足す」という操作を具体的に考えてみましょう。元の整数が $a$ で末尾に付け足す1桁の整数が $b$ だとすると、結果は $10a + b$ になります。これを順に繰り返すので、数字を付け足していく操作は足し算と掛け算だけで構成されていることになります。

そしてこのように足し算と掛け算だけで構成された計算の結果を13で割った余りは、計算の途中で出てくる数を13で割った余りに置き換えて同様に計算したものと同じになります。

※これは割る数が13に限ったものではなく、任意の正整数について言えます。また引き算でも、そして「逆元」というものを使えば割り算でも同じことが言えます。

例えば、列挙の途中で510という数があったとします。この末尾に 3 を付け足すと結果は5103になり、これを13で割った余りは7です。このように計算する代わりに、まず510を13で割って余り3を求めて、ここに 3 を付け足しても、33を13で割った余りは同じく7です。

この性質を使えば、列挙の途中でも数をまとめていくことができます。全ての数のパターンを具体的に持つ代わりに、「13で割って0余る数が○個」「13で割って1余る数が○個」という数え方をしていくのです。

f:id:betrue12:20190821235435p:plain

DPをしよう

このように「順番に見ながら、これまでの計算結果を利用して必要な値を計算していく」「同じとみなしても良い状態をまとめていく」という処理を実現するのが動的計画法（DP）です。

先ほどのまとめ方をそのまま状態にします。つまり持つべき状態は、

$dp\lbrack i \rbrack\lbrack j \rbrack$ = 前から $i$ 文字の時点で作れる数のうち、13で割った余りが $j$ であるものの個数

です。このDPの遷移を考えましょう。

$dp\lbrack i \rbrack\lbrack j \rbrack$ で数えられているのは、前から $i$ 文字の時点で作れる数で余りが $j$ の数です。この末尾に数 $b$ を付け足した数の余りは、 $10j + b$ を13で割った余りになります。これを $j_{2}$ として、 $dp\lbrack i+1 \rbrack\lbrack j_{2}\rbrack$ に遷移すればよいです。

f:id:betrue12:20190822001044p:plain

この $b$ としては、もし $S$ の $i+1$ 文字目が数字だったらその数。? だったら $b = 0, 1, ..., 9$ の10通りを全部遷移させてしまいます。

これを最後まで計算して、 $S$ の長さを $N$ として $dp\lbrack N\rbrack\lbrack 5 \rbrack$ が答えになります。

※ もし ? が非常に多い場合、この $dp\lbrack i \rbrack\lbrack j \rbrack$ がすごい数になってしまうかもしれません。しかし問題文には「答えは非常に大きくなる可能性があるため、 $10^{9}+7$ で割った余りを答えてください。」と書いてあります。そして遷移は全て足し算で計算できるので、先ほどの説明と全く同様の理由で、 $dp\lbrack i \rbrack\lbrack j \rbrack$ は随時 $10^{9}+7$ で割った余りに置き換えて良いです。これをしないとオーバーフローを起こすか、多倍長整数が扱える言語でも計算時間が悪化します。