Typical DP Contest_E_数

コンテストの名前の通りDPの問題.どのようにDPテーブルを更新するかが少し特徴的なのでブログにまとめておく.新規性は1ミリもありません.

問題の説明

$N$ 以下の正整数であり,十進表記したときの各桁の数の和が $D$ の倍数であるものの個数を[tex: mod 1,000,000,007 ]で求めよ.

条件

$1≦N≦10^10000$
$1≦D≦100$

考えた事

見ての通り $N$ がとんでもなく大きい.もちろん $N$ 毎に判定してcountするような $O(N)$ 解法が全く持って間に合わないのは火を見るよりも明らかだろう.

この問題に限らず,一般に調べるべきもののサイズが非常に大きいもの*1であるとき,string型に直して各桁について調べるアプローチが典型である.今回もそのようなアプローチを取る.つまり, $N$ を最大 $10000$ 桁の数とみて,その各々の桁の情報を使って問題を解く方針だ.

今回ならどのように見て行けばいいだろうか.もちろん素直に各桁の数字を決めていって全部試す方法では意味がない.どうすべきか.

例えば $N=1235, D=4$ であったとして,一々これを $1,2,3,4......1235$ と試すのはどう考えても無駄が大きい.これを変えたいのだ.ここでDPの考えが出てくる.先にDPテーブルをどう作ればいいかを見てもらおう.

$dp_{(確定桁数),(N未満確定かどうか),(問題の条件式)}$

として,DPテーブルに上の条件で満たしている数の個数を書き入れていくのだ

基本はこの形である.数を上の桁から決定していくように眺めるのだ.この場合だと千の位が $0$ か $1$ のどちらかで決定する.

イメージとしては配るDPを想像してもらえばいい.上の桁(例えば $0???$ )を決定していく事で,下の桁の情報が増えていく形だ.

千の位が $0$ である時,どうやっても $N$ を下回る事が確定しているので,残りの百の位,十の位,一の位で $4$ の倍数となるものは千の位が $0$ となるものから来ることが分かる.残りの桁の決定でも同様である.

千の位が $0$ であるとき,もちろん $N$ 未満確定なので,

$dp_{2,1,(問題の条件式)'}$ $+=$ $dp_{1,1,(問題の条件式)'}$

となる.明らかに桁の情報が増えたとしても元を辿れば前の桁の情報からきている.

今回であれば,各桁の合計がDで割り切れるかどうかなので,問題の条件式は各桁の合計 $j$ として

$dp_{1,1,j\bmod D}$

となる.上の例であるならば千の位は $0$ として進めているので, $j=0$ となる. $N=1235$ としているので1桁目は $0,1$ のいずれしか存在しない.つまり,

$dp_{1,1,j}=1(j=0, 1)$

$dp_{1,1,j}=(otherwise)$

の形である.

そして,上の桁が $0$ 確定であるものを, $dp_{2,1,(0+0)\bmod D}$ , $dp_{2,1,(0+1)\bmod D}$ , $dp_{2,1,(0+2)\bmod D}$ ,... $dp_{2,1,(0+9)\bmod D}$ に配っていくのだ.

ここで $0~9$ は何かというと二桁目,つまり百の位の数字であり,00~09の段階で条件を満たしているものは何個かというように見ている.

今回であると

$dp_{2,1,0} =3$

$dp_{2,1,1} =2$

$dp_{2,1,2} =2$

$dp_{2,1,3} =2$

となる.見て分かるようにさっきまで雑然としていたものが徐々にまとまってきている.

まだ終わりではない.今度は1桁目,つまり千の位が1のものを考える.千の位が $1$ であるとき, $N$ 未満確定かどうかは分からないため,

$dp_{1,0,1}=1$ となる.今度はこれを配っていく.

千の位が $1$ であり, $N$ を超えないように百の位を決めるとき,百の位の数として考えられる候補は $0,1,2$ であり,このうち $0,1$ は明らかに $N$ 未満確定する.

$(1+0)%D=1$ , $(1+1)\bmod D=2$ である事に注意すると,

$dp_{2,1,1} += dp_{1,0,1}$

$dp_{2,1,2} += dp_{1,0,1}$

のように配られ,結果,

$dp_{2,1,0} =3$

$dp_{2,1,1} =3$

$dp_{2,1,2} =3$

$dp_{2,1,3} =2$

となる.最後に,千の位が1,百の位が2であるものを考えると,これは $N$ 未満確定ではないため,

$dp_{2,0,(1+2)\bmod D}+=dp_{1,0,1}$

と配られる.つまり,

$dp_{2,0,3}=1$

となる.以上をまとめると,

$dp_{2,1,0} =3$

$dp_{2,1,1} =3$

$dp_{2,1,2} =3$

$dp_{2,1,3} =2$

$dp_{2,0,0}=0$

$dp_{2,0,1}=0$

$dp_{2,0,2}=0$

$dp_{2,0,3}=1$

となる.これは $N$ 以下となるよう上2桁を決める時の候補が $00~09,10,11,12$ の計 $12$ 個である事と一致している.

ポイントとなるのは桁数の合計を記録するのではなく,桁数の合計を $mod D$ で取った数を記録している事にある.こうする事で配列の幅を $D$ とし,情報の整理と計算量削減に成功している.

乱暴な言い方かもしれないが, $D=4$ であるとき, $022?$ と $026?$ と $035?$ と $116?$ が持つ情報量は全く同じであるから,1括りにまとめておくのが楽だというような解釈をすればいいだろう.これは楽であるだけでなく,こう1括りにまとめてしまう事で,計算量の幅を $O(10^{Nの桁数})$

から大きく落とし込める点でも有益である.

この纏めるというところが桁DPの真髄かもしれない.まず,前の桁を決定し問題の条件式に応じてまとめ,その次の桁にその情報(個数)を配り,またまとめ,また配りを繰り返していく.

今回であればまとめる作業は[tex:*2\bmod D]であり,これはただ剰余を求めているだけであるから $O(1)$ で行える.本来は $0~9$ で一々見て,各々の桁の和について一つ一つ考えるため,計算量は $O(N)$ であったところから比べると大きな進歩であろう.これを踏まえてコードに書き起こすと以下の通り.

ll n = N.size();
    vector<vector<vector<mint>>> dp(
        n + 1, vector<vector<mint>>(
                   2, vector<mint>(D, 0)));  // dp[桁数][N未満確定か][j % D]
    dp.at(0).at(0).at(0) = 1;  // 0桁目は0とみなすため,dp[0][0][0]=1
    rep(i, n) {
        rep(j, D) {
            rep(k, 10) {
                dp.at(i + 1).at(1).at[(j + k) % D] += dp.at(i).at(1).at(j);  
 //上から見てiより前の桁でN未満確定から考える.
            }
            ll keta = N.at(i) - '0';  // Nの上から見てi桁目
            rep(m, keta) {
                dp.at(i + 1).at(1).at[(j + m) % D] += dp.at(i).at(0).at(j);
            }
            dp.at(i + 1).at(0).at[(j + keta) % D] += dp.at(i).at(0).at(j);
        }
    }

初期条件として $0$ 桁目で $0$ であるとき, $N$ の0桁目は $0$ であるとみなして, $dp_{0,0,0}=1$ としている.

後はコードにある通り,上から桁を決め,Dの剰余の回数配り,新しい桁としてあり得るのは $0~9$ であるとしてループを回す.

計算量は $O(n×D×10)=O(10^8)$ となり,制限時間に間に合う.

答えとしては, $dp_{n,1,0}$ , $dp_{n,0,0}$ を合計したものから $1$ を引いたものとなる.

$dp_{n,1,0}$ は $n$ 桁目*3まで決めて $N$ 未満確定のもの( $0000~1234$ )で,各桁の合計を $D$ で割った余りが $0$ となるものの合計であり, $dp_{n,0,0}$ は $n$ 桁目まで決めて, $N$ 未満確定でないもの(これは実質 $N=1235$ のみを指す)の中で,各桁の合計を $D$ で割った余りが $0$ となるものの合計である.*4

$1$ を引く理由としては初期条件の部分で $dp_{n,0,0}=1$ としており,それが巡り巡って, $dp_{n,1,0}$ の中に $0000$ の個数1個分を余分に含む形となっているからである.問題文が「 $N$ 以下の非負整数で～」となっていた場合,この処理は行わなくていい.

いかがだっただろうか.正直,自分のプログラミングの力が足りなく,例に大きく頼った未熟な説明となってしまった.これが今の自分の限界である.

とはいえ,今の自分の力で精一杯,桁DPのアルゴリズムを説明できていると思う.これを読んだ誰かの理解の一助となる事を願っております.今回も最後までお読みいただきありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)

int main() {
    ll D;
    cin >> D;
    string N;
    cin >> N;
    ll n = N.size();
    vector<vector<vector<mint>>> dp(
        n + 1, vector<vector<mint>>(
                   2, vector<mint>(D, 0)));  // dp[桁数][N未満確定か][j % D]
    dp.at(0).at(0).at(0) = 1;  // 0桁目は0とみなすため,dp[0][0][0]=1
    rep(i, n) {
        rep(j, D) {
            rep(k, 10) {
                dp.at(i + 1).at(1).at[(j + k) % D] += dp.at(i).at(1).at(
                    j);  //上から見てiより前の桁でN未満確定から考える.
            }
            ll keta = N.at(i) - '0';  // Nの上から見てi桁目
            rep(m, keta) {
                dp.at(i + 1).at(1).at[(j + m) % D] += dp.at(i).at(0).at(j);
            }
            dp.at(i + 1).at(0).at[(j + keta) % D] += dp.at(i).at(0).at(j);
        }
    }
    mint sum = dp.at(n).at(0).at(0) + dp.at(n).at(1).at(0) - 1;
    cout << sum.val() << endl;
}

*1:多倍長整数というそうです

*2:今までの桁の合計\bmod D)+(新しい桁の数字

*3:もちろん,全ての桁を決定した事になる

*4:ここでは実質的に0か1となる

garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい

Typical DP Contest_E_数

問題の説明

条件

考えた事

プログラム