問題
正整数 の桁和を、
を10進法で表したときの各桁の和として定義する。
正整数 が
の桁和で割り切れるとき、
を良い整数と呼ぶ。
正整数 が与えられるとき、
以下の良い整数の個数を求めよ。
入力
最初の1行に、正整数 が与えられる。
条件
- 実行時間制限: 10s
- メモリ制限: 1024MB
出力
答えとなる個数を1行で出力すること。
解法
この問題では、これまでのAtCoderの問題と比較すると実行時間制限が10sとかなり緩めなので、まずは計算量についてあまり考えずに解くことを考えます。
ただし、 であるので、
以下のすべての整数に対して桁和を計算し、それが良い整数となるのかを判断することはできません。
そこで、
以下の整数の桁数は最大で
桁であることから、DPを用いて個数を管理することを考えます。
ここで、まずは最終的に得られる整数の桁和の値を固定して考えます。（以下、この桁和の値を とします。）
その上で、 を整数について上から
桁目までを決定したときに、桁和が
であり、その整数の
での値が
である整数の個数として定めます。
（このときに、整数が
以下かどうかについては今はまだ考えないこととします。）
現在考えている値の全体の桁数が であるとして、このときに上から
桁目までの
の値が全て決定されているとします。
ここに、 次の
桁目として
が追加されるとします。
このとき、 桁目の時点で桁和が
であった整数は、
桁目の時点で桁和が
となります。
また、本来の整数としては元の考えていた整数に対して が加えられることになるので、
桁目の時点で
での値が
である整数は、
桁目の時点で
での値が
となります。
以上から、 \begin{align} \mathrm{dp}_{i, \, j + l, \, (k + l \cdot {10}^{d - i}) \, \% \, s} \leftarrow \mathrm{dp}_{i, \, j + l, \, (k + l \cdot {10}^{d - i}) \, \% \, s} + \mathrm{dp}_{i - 1, \, j, \, k} \end{align} という更新が行えると言えます。
ここで、 桁目の値として考えられる値は
から
までのすべての整数であることから、
です。
従って、すべての
に対して
として値を更新することで、
の値が得られるということが言えます。
この問題では、 であることから、桁和の最大値として考えられるのは
です。
そのため、
の最大値は
であり、
の最大値は
であることから、この更新を行うことによるおおよその計算回数は、
\begin{align}
15 \times 126 \times 126 \times 10 = 2381400
\end{align}
ということになります。
これは の値を固定したときの回数であり、
でもあることから、全体でのおおよその計算回数は,
\begin{align}
2381400 \times 126 = 300056400 \fallingdotseq 3 \times {10}^{8}
\end{align}
ということになります。
この問題の実行時間制限は10sと緩めに設定されていることから、この方法で実行時間制限には間に合いそうということが言えます。
さて、ここからは 以下の整数に限る場合、ということについて考えます。
先ほどの では、考えている値について
以下であるという保証がなされていません。
そこで、添字については同じものとして、
を「考えている値が
未満に必ずなるときの個数」とし、
を「考えている値が
になりえるときの個数」として定義します。
が
桁の整数であるとして、このときに上から
桁目までの
の値が全て決定されているとします。
そして、
の上から
桁目の値が
であるとします。
このとき、まずは についてはその後にどのような整数が
桁目として追加されても確実に
未満の値となることから、
に対して、先程の
と同様にして、
\begin{align}
\mathrm{dp 1}_{i, \, j + l, \, (k + l \cdot {10}^{d - i}) \, \% \, s} \leftarrow \mathrm{dp 1}_{i, \, j + l, \, (k + l \cdot {10}^{d - i}) \, \% \, s} + \mathrm{dp 1}_{i - 1, \, j, \, k}
\end{align}
という更新が行えます。
また、 桁目までは
になるかもしれない整数についても、
桁目として
未満の数字が入る場合は確実に
未満の整数となります。
従って、
の値を用いて、
を満たすすべての
に対して、
\begin{align}
\mathrm{dp 1}_{i, \, j + l, \, (k + l \cdot {10}^{d - i}) \, \% \, s} \leftarrow \mathrm{dp 1}_{i, \, j + l, \, (k + l \cdot {10}^{d - i}) \, \% \, s} + \mathrm{dp 2}_{i - 1, \, j, \, k}
\end{align}
という更新が行えます。
最後に、 桁目までは
になるかもしれない整数に対して、
桁目として
が入る場合については、
の値の更新になるので、
\begin{align}
\mathrm{dp 2}_{i, \, j + {a}_{i}, \, (k + {a}_{i} \cdot {10}^{d - i}) \, \% \, s} \leftarrow \mathrm{dp 2}_{i, \, j + {a}_{i}, \, (k + {a}_{i} \cdot {10}^{d - i}) \, \% \, s} + \mathrm{dp 2}_{i - 1, \, j, \, k}
\end{align}
という更新が行えます。
以上の更新を考えられる に対して行うことで、
が全て得られます。
求めるものは、 以下の整数のうち、桁和が
であり、
で割り切れるものの総数なので、
を
桁の整数とすると、
となります。
これを考えられるすべての
に対して導出し、それらの総和が求める答えとなります。
また先程も書きましたが、この問題の実行時間制限は10sと緩めに設定されているので、この方法で実行時間制限に間に合うと言えます。
ソースコード
引数として sum を与えたときに、桁和が sum かつ sum で割り切れる 以下の整数の個数を返す関数
solve() を以下のように実装しました。
ll n, dp1[20][150][150], dp2[20][150][150]; ll solve(int sum) { // rest は現在見ている桁での値を導出するために用いる // digit は上から見たときに現在 10^i の桁を考えているのか、という整数を表す // digit_cnt は n の桁数を表す ll rest = n, digit = 1, digit_cnt = 1; while (digit * 10 <= n) { digit *= 10; digit_cnt++; } // 上から0桁目の段階ではまだ n になりえるので、 dp2[0][0][0] = 1 としておく dp2[0][0][0] = 1; for (ll i = 1; i <= digit_cnt; i++) { // dp1 を用いた dp1 の更新 for (ll j = 0; j < 150; j++) { for (ll k = 0; k < 150; k++) { for (ll l = 0; l <= 9; l++) { dp1[i][j + l][(k + l * digit) % sum] += dp1[i - 1][j][k]; } } } int l_max = rest / digit; // l_max は先ほどの説明での a[i] に該当する // dp2 を用いた dp1 の更新 for (int j = 0; j < 150; j++) { for (int k = 0; k < 150; k++) { for (int l = 0; l < l_max; l++) { dp1[i][j + l][(k + l * digit) % sum] += dp2[i - 1][j][k]; } // dp2 の更新 dp2[i][j + l_max][(k + l_max * digit) % sum] += dp2[i - 1][j][k]; } } rest %= digit; // rest を 10^i で割った余りを求めることにより、次の位に移行しやすくする digit /= 10; // 次の位を考えるために、 digit を 10 で割る } // 値を返す return dp1[digit_cnt][sum][0] + dp2[digit_cnt][sum][0]; }
感想
実行時間制限が10sとなっていたので、最初見たときはビビりました。
整数に対してのDP問題は久しぶりでした。 いつか、EDPC の解説でも触れると思います。
