TechFULの中の人

triple-four’s blog

桁DP入門

TechFUL

こんにちは！ TechFULで問題制作アルバイトをしているganariyaです。
自分はよく桁DPについて、こちらの記事(Re:桁DPのこと)で勉強させていただいていたのですが、ようやく自分の中に身についてきたので、これから桁DPを学習しようという方に向けて、できるだけ分かりやすく桁DPについてまとめてみようと思います！

そもそもDPとは？

DPとは、Dynamic Programmingの略であり、日本語では動的計画法と呼ばれています。
動的に値を配列などに保存しながら、その値を再利用することで効率的に答えを求めることが出来ます。

DPの有名問題では

などが有名ですね。DPについて知りたい方はこちらの記事(典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～)を参照すると、非常にわかりやすいと思います。

桁DPとは？

桁DPは、その名の通り桁に関するDPです。
桁DPを知っている人が、桁DPを利用する問題を見ると「あっ･･･」と一瞬で桁DPだと分かることが多いです。

例えば、以下のような問題。

とある整数Nが与えられる。N以下の自然数のうち、各桁の数の和がDとなる数の個数を10^{9}+7で割った余りを求めよ。 制約(1{\leqq}N{\leqq}10^{100}, 1{\leqq}D{\leqq}10^{3})

例えば、N=1000のときは、1~Nについて、それぞれの各桁の和を求めて、その和がDかどうかを調べればいいです。

桁DPを桁DPたらしめる理由を以下にまとめてみます。

桁に関している

当たり前ですが、基本的には桁に関しての問題です。今回の問題では、各桁について和を求める必要があるため、桁DPと分かります。

制約が大きい

上記の問題では、制約がNの制約が1{\leqq}N{\leqq}10^{100}です。10^{100}は大体の言語で数が大きすぎて扱うことはできません。例えばC++ではlong long型でおおよそ10^{19}ぐらいなので、整数型として扱うことが出来ないことが分かります。

全探索できない

当然ですが、10^{100}は全探索することができません。10^{8}でおよそ1秒かかるため、10^{100}は到底時間内に終わる計算ではありません。10^{4}ぐらいだったら素直に全探索しても現実的な時間で終了するので、全探索していいと思います。

例題1つ目を見てみる

ちょっと上の問題は難しいので、もっと簡単な問題を考えてみます。
例えば、以下のような問題です。

とある整数Nが与えられる。N以下の自然数の個数を10^{9}+7で割った余りを求めよ。
制約(1{\leqq}N{\leqq}10^{6})

とてもシンプルな問題です。各桁の和がDとなるという条件も消え、制約も106とゆるゆるになりました。
というか、N以下の自然数は全て条件を満たすので、答えはNです。N=1000なら、答えは1000です(当たり前ですが)。

ただ、それだと何も得られないので、桁DPの解き方でこの問題を解いてみようと思います。

1. 整数を文字列として扱う

一番最初の問題では、N=10^{100}であり、数が大きすぎてとても整数型として扱うことができません。
そのような場合は文字列Sとして扱ってしまいましょう。
整数型ではないので、他の数との足し算はできませんが、個数を数えるだけなので文字列で問題ありません。

･･･各桁の値を求められなくなるのではないか？という声もありそうですが、大丈夫です。S[i]-'0'としてしまえば、各桁の値を求めることが出来ます。

#include <string>
#include <iostream>
#include <cstring>

using namespace std;

int main() {

    //文字列Sとして格納
    string S;
    cin >> S;

}

2. 再帰を用いて答えを求める

桁DPでは、上位の桁から、再帰関数を用いて計算することが多いようです。for文でも実装できるようですが、難しいので再帰関数で考えます。

桁DPは、上下関係のある職場と捉えるとある意味わかりやすいかもしれません。 例えば、一番左側の上位の桁は社長で、一番右側の下位の桁は平社員です。
上位から下位にかけて、 立場が低くなると思ってください。
社長は、部下に対して「私より右側にある桁の数の中で、条件を満たす整数の個数を数えてくれ」と言います。その部下は、さらに地位の低い人に対して、「私より右側にある桁の数の中で、条件を満たす整数の個数を数えてくれ」と言い、下の地位の人への責任転嫁が続きます。
そして、一番右側の桁の地位の弱い人は、仕事を責任転嫁できる人がいません。よって、自分が条件を満たす整数かどうかの1か0を返します。 最後に、ある人が立場の弱い部下から答えを受け取ると、その答えをまとめ上げて(全て足して)、自分がまるでやったかのように、上司に「やっておきました〜〜」とその答えの和を返します。汚いですね。
最後に、社長がすべての条件を満たす整数の個数をプログラマーに返して再帰関数は終了します。

上記の考えは、再帰に非常に似ています。部下に仕事を任せて、部下がやった仕事を上司に返す･･･再帰そのものです。

下の画像がそのイメージです。

f:id:ganariya:20180920151056p:plain
上下関係

一度全ての内容を読んでから、またここに帰ってきたとき、なんとなく意味が伝われば嬉しいです。

#include <string>
#include <iostream>
#include <cstring>

using namespace std;

//再帰関数
int rec(string &S){
    
}

int main() {

    //文字列Sとして格納
    string S;
    cin >> S;
    
    //答えが返ってくる
    cout << rec(S) << endl;

}

3. 数の性質を利用する

ここで、ちょっと一度一番最初の問題に立ち返ってみます。
1〜Nの整数の中で、各桁の和がDとなるような数の個数を求める問題です。 例えば、N = 572353、D = 16を考えます。 これから、大事な性質について述べていきますが、桁DPでは

  • 上位の桁から下位の桁に向かって、仕事を任せる。(自分の桁より右側の数に、Dの条件を満たす個数を求めさせる。)
  • 一番下位の桁までたどり着くと、仕事を任せられる右の桁がいないので、Dの条件を満たすかを、左の桁に向かって返す。
  • 右側の桁から答えを受け取ると、その答えをまとめ上げて、左側に返す。

の上記の意識を忘れないでください。

　性質１: 上位の桁から下位の桁を見る時、上位からの状態が大事である。

例えば、N=572353以下という条件をを満たす数 545---について考えてみます。-はまだ判明していない数です。

上位の桁から5-----から、下位の桁へ仕事が投げられて545---までやってきました。
545---は一番右側の桁まで判明していないため、右側の桁へ仕事を投げたいです。 そこで5450--、5451--、5452--、5453--、･･･、5459--と右側の桁に、「各桁の和がDの条件を満たす数を返せ！」と責任転嫁します。
そして、5450--は、54500-、54501-、･･･、54509-と、再び右側の桁に仕事を投げていきます。
このように仕事を投げることで、一番下位の545000~545999まで調べられそうです。

ここで、最終的に545---が下位の桁から受け取る答えは6となります。 なぜならば、545---の数を全て探索しても、各桁の和がDの条件を満たす数は以下の6つしかないからです。

  • ５４５００２
  • ５４５０２０
  • ５４５２００
  • ５４５１１０
  • ５４５１０１
  • ５４５０１１

なるほど、545---では以上の6つしか、Dの条件を満たさないようです。
では、例えば他の数394---では、Dの条件を満たす個数は何個あるのでしょうか。

実はこれも答えは6つです。以下の6つがあります。

  • ３９２００２
  • ３９２０２０
  • ３９２２００
  • ３９２１１０
  • ３９２１０１
  • ３９２０１１

･･･どうしてDの条件を満たす個数が同じになったのでしょうか。
それは、以下の理由があります。

  1. これまで見てきた上位の桁の和が両方14だった。
  2. これまで見てきた上位の既に使用している桁が3つだった。

1の理由から見ていこうとおもいます。
545---は、54----から「545---以降の数でDの条件を満たす数を求めてくれや！」と責任転嫁されました。392---も、「392---以降の数でDの条件を満たす数を求めてくれや！」と責任転嫁されています。
ここで、545---ならすでに見てきた5、4、5の数の和は14です。392---なら、3、9、2で14です。
上位の桁の和が同じなら、答えは一緒になることがわかります。両方---に入るのは000~999で同じ組み合わせだからです。
答えが一緒になるということは、値を一度計算すれば配列に保存して再利用できるということです。

ただし、2の理由も大切で、忘れてはいけません。 例えば、5252--を考えてみます。5252の和は14のため、545---や392---と同じ6になりそうです。しかし、実際は違います。以下の3つしか存在しません。

  • ５２５２０２
  • ５２５２２０
  • ５２５２１１

答えが異なる理由は、すでに見てきた上位の桁の個数が違うからです。545---では3つしか見ていませんが、5252--では、すでに4つも見ています。見れば見るほど、自由(-で表される)な下位の桁の個数が減るため、Dの条件を満たす個数が減っていきます。

よって、これらの理由から、桁DPでは上位の桁からの状態(上位の桁までの和や、どこまで見たかなど)が大事であることを意識してください。

　性質２: 上位の桁から仕事を任された時、自由度(tight)が大きいかどうかが大事である。

こちらも大事な性質なのですが、既に見てきた上位の桁の時点で、自由度が大きいかどうかが大事となってきます。

性質１同様、N=572353以下という条件をを満たす数について考えてみます。 例えば、572---の責任転嫁できる数について考えてみます。以下のようになります。

  • ５７２０ーー
  • ５７２１ーー
  • ５７２２ーー
  • ５７２３ーー

以上の6つがあります。5724--などは、元のN=572353の数を超えてしまうため、求めることができません。

しかし、522---の責任転嫁できる数について考えてみます。以下のようになります。

  • ５２２０ーー
  • ５２２１ーー
  • ･･･
  • ･･･
  • ５２２９ーー

以上の522---では、10つも責任転嫁できました。522---と572---の違いは何なのでしょうか。
それは、すでに見てきた上位の桁の時点で自由になっているかいないかの違いです。
ここで言う自由とは、すでに見てきた上位の桁の時点で、これ以降の下位の桁にどんな数を設定したとしても、N以下といえるかというものです。

ちょっとよくわからないと思うので、詳しく見ていきます。
572---では、これまで見てきた572はN=572353と完全に一致しています。そのため、責任転嫁するとき、間違って5728---などとしてしまうと、N=572353を超えてしまいます。
そのため、572---は、まだ自由になっておらず、N=572353に合わせて0~3の4つにしか責任転嫁できません。

しかし、522---は既に自由になっています。上位から見て二桁目の2が、N=572353の7より小さいからです。5229--と遷移しても既に自由になっているため、自由に0~9に責任転嫁できます。Nに縛られることがないのです。

よって、これらの理由から、既に見てきた上位の桁が自由かどうかが大切です。自由なら、これまで見てきた数の時点で既にNより小さいことが分かっているため0~9の全てで右側に責任転嫁できます。しかし、自由でないなら、Nを超えないように責任転嫁しないといけません。

4. 実際のコードを見てみる

実際のコードを見てみます。

#include <string>
#include <iostream>
#include <cstring>

using namespace std;

//rec関数
//0~k桁目までの状態を踏まえて
//k+1桁目以降に、個数を求めろ！と責任転嫁する。
//その後、k+1桁目から受け取った答えをまとめ上げて、k-1桁目に返す。
//つまり、自分(k)を含むk桁目以降の条件を満たす個数を返す。

//k
//現在見ている桁の位置を表す。0-indexなのに注意。

//tight
//これまで見てきたk-1桁目までで、自由かを判定する
//trueなら自由じゃない(厳しい)
//falseなら自由(0~9に自由にできる)

int rec(string &S, int k = 0, bool tight = true) {

    //これ以上責任転嫁できないので
    //これまで見てきた書く桁の状態を踏まえて1か0を返す。
    //今回は、条件が特に無いので強制的に1を返している。
    if (k == S.size()) {
        return 1;
    }

    //k桁目の数字を取り出す。
    int x = S[k] - '0';

    //k-1桁目までの状態で
    //厳しく自由じゃない(true)なら、xまでしか責任転嫁できない(Nを超えてしまうため)
    //自由(false)なら、上位の桁の時点でNより小さいことが証明されているため、0~9に責任転嫁できる。
    int r = tight ? x : 9;

    //自分を含むk桁目以降の、条件を満たす個数を格納する。
    //しかし、実際は自分で計算せず、k+1桁目以降に計算させて、その結果をまとめ上げるだけ
    int res = 0;

    //k+1桁目以降に責任転嫁し、その結果をまとめ上げる
    //tight=trueなら0~xまでしか遷移できないが
    //falseなら0~9まで遷移できる
    for (int i = 0; i <= r; i++) {

        //tight && i==rは
        //下位の桁に責任転嫁するとき、k桁目で自由かどうかを渡している
        //k-1桁目までで既にtight=falseなら &&演算を行った時点で強制的にfalse(自由)になる。
        //しかし、k-1桁目まででtight=trueかつ、i==r(k+1桁目以降も自由じゃない)ときはtrueになってしまう。
        res += rec(S, k + 1, tight && i == r);

    }

    return res;
}

int main() {

    //文字列Sとして格納
    string S;
    cin >> S;

    //答えが返ってくる
    cout << rec(S) << endl;

}

よくわからないと思うので部分的に見ていきます。

桁を自由度にあわせて取得する

int rec(string &S, int k = 0, bool tight = true) {

    //k桁目の数字を取り出す。
    int x = S[k] - '0';

    //k-1桁目までの状態で
    //厳しく自由じゃない(true)なら、xまでしか責任転嫁できない(Nを超えてしまうため)
    //自由(false)なら、上位の桁の時点でNより小さいことが証明されているため、0~9に責任転嫁できる。
    int r = tight ? x : 9;

}

まず、最初はk桁目の数を取り出します。一行目のプログラムですね。
main関数で呼び出すときはデフォルト引数を利用して、0桁目からにしています。ここで注意するべきことは、文字列の左側から0桁目という0-indexであることに注意してください。

そして、k-1桁目までの状態を表すtight変数によって、現在のk桁目が自由かどうかで変数rの値が決まります。
もし、k-1桁目までで自由(すでにNより小さいと保証されている)ならrは0~9となり、自由でないなら0~xとなります。

k桁目以降の条件を満たす個数をまとめ上げる

int rec(string &S, int k = 0, bool tight = true) {

    //自分を含むk桁目以降の、条件を満たす個数を格納する。
    //しかし、実際は自分で計算せず、k+1桁目以降に計算させて、その結果をまとめ上げるだけ
    int res = 0;

    //k+1桁目以降に責任転嫁し、その結果をまとめ上げる
    //tight=trueなら0~xまでしか遷移できないが
    //falseなら0~9まで遷移できる
    for (int i = 0; i <= r; i++) {

        //tight && i==rは
        //下位の桁に責任転嫁するとき、k桁目で自由かどうかを渡している
        //k-1桁目までで既にtight=falseなら &&演算を行った時点で強制的にfalse(自由)になる。
        //しかし、k-1桁目まででtight=trueかつ、i==r(k+1桁目以降も自由じゃない)ときはtrueになってしまう。
        res += rec(S, k + 1, tight && i == r);

    }

    return res;
}

現在見ているk桁目以降の条件を満たす個数をまとめ上げるために、res変数を用意して0で初期化します。
そして、先程用意したr変数に合わせてfor文を実行しています。
これは、右側の桁に「自分を含めた左側の桁でtightな状態だ！あとは求めといて！」の責任転嫁の部分を実行しています。
そして、k+1桁目が集めてきた結果をres変数にまとめ上げて、あたかも自分で求めたかのようにreturnしています。

tight && i==rの部分ですが、すでにtight=falseで自由なら、i==rは関係ありません。tight & i==r がtrueになるのは、左側の桁が厳しい(Nより小さいと保証できてない)かつ、現在のk桁目でもNより小さいと保証できていないという状態です。

このままだと永遠に責任転嫁(再帰)してしまうので、再帰を返す部分を作る

int rec(string &S, int k = 0, bool tight = true) {

    //これ以上責任転嫁できないので
    //これまで見てきた書く桁の状態を踏まえて1か0を返す。
    //今回は、条件が特に無いので強制的に1を返している。
    if (k == S.size()) {
        return 1;
    }

}

このままのコードだと、再帰が終わらないため、強制的に値を返す部分を作成します。
それはk==S.size()で取ることが出来ます。0-indexのため、S.size(文字列の個数)にkがなっているときは、既に全ての桁を見てきたことを表します。
よって、それまでの左側から受け継いだ状態を踏まえて、条件を満たすかを1か0で判断すればいいです。
今回は強制的に全てが条件を満たすので1を返しています。

これが、桁DPの土台となるコードとなります。

例題1つ目から分かる考え方

例題1つ目から分かることは、以下のことです。

  • 桁DPとは、再帰を利用し、右側の桁に責任転嫁し、その結果をまとめ上げて左側に返している。
  • 上位からk桁目を計算するときは、k-1桁目までの自由度や状態が大事である。
  • rec関数は、k桁目を含む右側の桁の中で、条件を満たすものの個数を返す(但し、実際には自分で計算せず、右側に転嫁している。)

また、画像で例題1の考え方を表すと以下の様になります。

f:id:ganariya:20180920151239p:plain
まとめ上げ

例題2つ目を見てみる

とある整数Nが与えられる。N以下の自然数のうち、各桁の数の和がDとなる数の個数を10^{9}+7で割った余りを求めよ。 制約(1{\leqq}N{\leqq}10^{100}, 1{\leqq}D{\leqq}10^{3})

この問題に返ってきました。
今なら、初めて見たときよりはずいぶん解けそうな気がします。

例題1を踏まえて、ソースコードを書いてみます。

#include <string>
#include <iostream>
#include <cstring>

using namespace std;

//sum変数が増えた
int rec(string &S, int D, int k = 0, bool tight = true, int sum = 0) {

    if (k == S.size()) {
        return sum == D;
    }

    int x = S[k] - '0';

    int r = tight ? x : 9;

    int res = 0;

    for (int i = 0; i <= r; i++) {

        //k桁目の値iをsumに追加している
        res += rec(S, D, k + 1, tight && i == r, sum + i);
        res %= MOD;

    }

    return res;
}

int main() {

    //文字列Sとして格納
    string S;
    cin >> S;

    //D変数
    int D;
    cin >> D;

    //答えが返ってくる
    cout << rec(S, D) << endl;

}

これまでのソースコードとどこが変わったでしょうか。
一番大きく変わったのはsum変数が引数に追加されたことです。

k桁目以降の条件を満たす個数を求めるとき、sum変数にはk-1桁目までの桁の総和が入っています(前の桁までの状態が大切です)。 そして、for文でk桁目の桁の和iも足して、k+1桁目に仕事を責任転嫁しています。

そして、全ての桁を見終わったらk == S.size()のif文内で、sum == Dをしています。
これは、0~S.size()-1桁目までの桁を見てきた状態がsumやtightに入っています。それらの結果を踏まえて、Dと等しいかどうかを返してあげればいいです。

意外と、Dの条件がついても、あまり変わっていないですね。
Dの条件に対応するために、引数を増やしてk-1桁目までの状態を管理しているといっても過言ではありません。
条件が複雑になっても引数を適切に増やして、k==S.size()のif文で正しいか正しくないかを管理するだけで対応できそうです。

･･･ただし、このままではいけません。N=4383813819319、D=32などを実行してみてください。これはきっととてつもない時間がかかってしまうと思います。
なぜなら、このままでは全探索を行っているため、10を桁の数だけ累乗している計算量になってしまうからです。
このままでは到底現実的な時間で解けません。そこで、DPを利用します。

短時間で解くためにDPを追加する。

まずは全体のソースコードを見てみます。

#include <string>
#include <iostream>
#include <cstring>

using namespace std;

//dp[k][tight][sum]
//k-1桁目までで、tightでsumな状態であるとき
//k桁目以降の条件を満たすものをdp[k][tight][sum]に格納する。
int dp[110][2][1010];

int rec(string &S, int D, int k = 0, bool tight = true, int sum = 0) {

    if (k == S.size()) {
        return sum == D;
    }

    int x = S[k] - '0';

    int r = tight ? x : 9;

    //k-1桁目までで、tightでsumな状態であるとき
    //k桁目以降の条件を満たすものをdp[k][tight][sum]に格納
    //res変数で参照している
    int &res = dp[k][tight][sum];

    //すでに値が決まって入れば、これ以上探索する必要はないためこの時点で返してあげる
    if (~res) return res;

    //決まってなければ0に初期化してあげる
    res = 0;

    for (int i = 0; i <= r; i++) {
        res += rec(S, D, k + 1, tight && i == r, sum + i);
        res %= MOD;
    }

    return res;
}

int main() {

    //文字列Sとして格納
    string S;
    cin >> S;

    int D;
    cin >> D;

    //-1に初期化
    memset(dp, -1, sizeof(dp));

    //答えが返ってくる
    cout << rec(S, D) << endl;

}

いくつかポイントを述べていきます。

配列dpを用意する。

上記のソースコードでは、dp[110][2][1010]として配列を用意しています。
これはdp[k][tight][sum]を表し、k-1桁目までで、tightでsumな状態であるとき 、k桁目以降の条件を満たすものをdp[k][tight][sum]に格納します。

どうしてこういうことをして良いかというと、「例題1つ目をみてみる」の性質1を見ると分かります。

  • これまでのk-1桁目までの合計が同じ
  • これまでのk-1桁目までの自由度tightが同じ

である場合、見てきた桁の個数も合計も自由度も同じであるため、k桁目以降の条件を満たす個数は一致します。 よって、dpに格納してよいです。

参照でdpにアクセスする。

    //k-1桁目までで、tightでsumな状態であるとき
    //k桁目以降の条件を満たすものをdp[k][tight][sum]に格納
    //res変数で参照している
    int &res = dp[k][tight][sum];

    //すでに値が決まって入れば、これ以上探索する必要はないためこの時点で返してあげる
    if (~res) return res;

    //決まってなければ0に初期化してあげる
    res = 0;

上記のres変数の部分です。C++の参照機能を利用しています。
こうすることで、自分で後でresを適切な場所で設定しなくてもfor文でまとめ上げるときに自動でdp配列に値が反映されます。

また、if(~res)に注目してください。
実はmain文内で、dp配列を全て-1に設定しています。
どうしてかというと、-1は2進数で表すと111･･･11というように全て1になります。 そのため、~(ビット反転)を行うと-1は0になります。
よって、値の更新が行われていないときはif(0)となり、値の更新があればif(1)となり、簡単に既に値が設定されているかを判断することが出来ます。

決まっていなければres = 0として初期化してあげれば良いです。

以上のようなポイントを利用することで、シンプルにすばやく計算でき、実行してみれば分かりますが、速度がまるで違うことが実感できると思います。

例題2つ目から分かる大事な点

例題2つ目の前半からは以下のポイントが分かります。

  • 引数に、条件を満たすための変数を用意する。
  • k == S.size()で、全ての桁を見終わった時、引数を利用して条件を満たすかどうかを0か1で返す。

例題2つ目の後半からは以下のポイントが分かります。

  • そのまま実行すると計算量が大きいため、DPを利用する。
  • DPはdp[現在の桁k][k-1桁目までの状態tight][k-1桁目までの状態変数]とする。
  • 参照を利用して、シンプルに記述できる。

です。
ここで、特に大事なことは、条件Dなどを判断するために再帰関数の引数を増やし、dpの[桁][tight][条件のための変数]とすることだと思います。

まとめ

非常に長くなっていまいました･･･
桁DPは、最初はよくわからないですが、一度理解してしまうと解きやすい分野になります。特に、自分でノートなどに手を動かして、ある程度小さいケースを全部書いて試してみると非常に頭に入りやすく理解しやすいと思います。
間違っている点や、よくわからない点があればコメントで書いていただけると幸いです！ ガナリヤの桁DP入門でした！