桁DPの痒いところに手が届く解説

#はじめに
本記事は、アルゴリズムの一つである桁DPについて、入門者が疑問に感じる（というか筆者が実際疑問に感じた）ポイントに重点を置いて解説するものです。
筆者自身そこまで桁DPに詳しいわけではなく、むしろ最近覚えたぐらいなので、何かまずい部分があれば優しくご指摘いただけると嬉しいです。

この記事で特に重点を置くポイントは、次の通りです。

• 何故これでうまくいくのか
• 桁DPで数えているものは何か
• 初期条件はなぜこうなるのか

桁DPそのものの入門的解説としては、他にもけんちょんさん達の優れた記事がありますので、そちらも合わせてご覧ください。
http://torus711.hatenablog.com/entry/20150423/1429794075
http://drken1215.hatenablog.com/entry/2019/02/04/013700
https://pekempey.hatenablog.com/entry/2015/12/09/000603

#桁DPとは
まず、桁DPについて解説を行います。
桁DPは、

• 「０以上N以下の整数で、ある条件を満たすものの個数を求めよ」
• 「０以上N以下の整数で、ある条件を満たすものの最大値を求めよ」

といった問題を解く場合に用いられる方法です。
具体例で言うと、

• 「０以上N以下の整数で、いずれかの桁に3を含むものの個数を求めよ」

といった感じです。
以下、この例で少し考えてみましょう。

#手で数えてみる
桁DPの考え方は、いきなり天から降ってくるタイプのものではありません。
「手で数える」という原始的な方法から出発して、それを体系化することで得られる手法です。

まず、上の問題でN=123の場合を考えます。
最もナイーヴな方法としては、3のつく数を小さいものから順に列挙するという方法があります。
しかし、

3, 13, 23, 30, 31,..., 39, 43, 53,...

少し考えただけで、これはしんどい方法だと分かります。
プログラムにやらせるにせよ、N=10^9以上のオーダーになると、この方法では間に合わなくなります。
（ちなみに、実際の問題ではN=10^100とかの場合も普通にあります）

###大雑把な見積もり
そこで、もう少し効率のよい方法を考えます。
条件が桁に絡んでいるので、桁ごとに数えるという発想は自然です。
まず、N=123の百の位が1なので、候補となる数字の百の位は0か1の2つだけです。

次に、十の位を考えます。ざっくり言って、十の位は0から9まで動けます。
この各数字に対して、一の位が3だった場合に条件を満たすので、合計10個の数が条件を満たすと考えられます。
ところが、十の位が3だった場合のみが特殊で、この場合は一の位が何であっても条件を満たすので、さらに10個が追加されます。

結局、百の位2パターンに対し、下二桁で計20個程度の条件を満たす数が存在するので、大体2×20=40ぐらいが答えになるのではないかと予想できます。

###正確な数え方
これはかなり大雑把な見積もりだったので、この方法をより精密にしましょう。
まず、十の位が動ける範囲について。
先程、十の位が0から9まで動けると言いましたが、これは厳密には間違いで、動ける範囲は百の位の数字によります。
N=123以下という制限があるため、もし百の位が1だったならば、十の位は0から2までしか動けないことになります。
一方、もし百の位が0だったならば、今度は十の位は0から9まで動くことができます。

同様に、一の位が動ける範囲も、百の位と十の位の数字によります。
百の位が1、十の位が2だった場合、制約により一の位は0から3までしか動くことが出来ません。
それ以外の場合は、0から9までフルに動くことが出来ます。

さて、これで正確な答えを求める準備が整いました。
これまでの状況を整理したのが下の図になります。

十の位のところでは、便宜上3を分けて書きました。

図の上から順に数えていきましょう。
まずは一番上。百の位が0固定、十の位が3を飛ばして0から9まで動き、そのそれぞれに対して一の位が0から9まで動きます。
その中で、いずれかの桁に3が含まれるのは一の位が3になったときだけなので、結局このパターンでは9×1=9個の条件を満たす数があります。
十の位で3が飛ばされていることに注意してください。

次は、百の位が0固定、十の位が3固定です。
このとき、一の位は0から9まで動きます。
この場合、一の位が何であっても条件を満たすので、結局このパターンでは1×10=10個の条件を満たす数があります。

以下同様に数えていくと、最終的な答えは

9×1 + 1×10 + 2×1 + 1×1 = 22

となります。これが正真正銘、正確な答えです。
上で大雑把に見積もったときとは、約２倍も差が出てしまいました。

#アルゴリズムにしよう
###未満フラグ
これまでにやったことを、アルゴリズムとして形にしましょう。
核となるアイデアは、「桁ごとに数える」ということです。しかし問題となるのは、上で見た通り、「上の位の数字によって下の位が動ける範囲が変わる」という事情です。

このことは、条件を満たす数を数えるときに、数えるための変数に一種の「状態」を持たせなければならないことを意味しています。
より具体的に言うならば、「今調べている桁より上の桁の数字が、Nの対応する桁の数字と同じになっているかどうか」を表すフラグが必要ということです。
例えばN=12345で、今調べているのが百の位であるとき、上位の桁が

12***

の形をしているのか、それ以外なのかをフラグで管理する必要があるということです。
また、フラグの性質上、カウントは上位の桁から順に行わなければならないことも分かります。

このフラグを**「未満フラグ」**といいます。

###既に3が出たかどうかのフラグ
必要なフラグはこれだけではありません。「いずれかの桁に3を含む」数を数えているのですから、「（上位の桁で）既に3が出たかどうか」のフラグが必要です。
もし上位の桁で既に3が出ていたならば、現在調べている桁の数字が何であろうと、その数は条件を満たすからです。
逆に、まだ3が出ていないならば、現在調べている桁の数字が3でないと条件を満たしません。

以上のことを考え合わせて、今調べている桁をi、未満フラグをsmaller、3が出たかどうかのフラグをjとすると、数える変数は

dp[i][smaller][j]

というような配列の形を取らねばならないことが分かります(未満のときsmaller=1、3が出ているときj=1)。

###配列dpの定義
では、この配列dpはどう定義されるべきでしょう。それは、

dp[i + 1][smaller][j] = (上からi桁目までで条件を満たす数の総数)

です。ただし、ここで言う「条件」とは、「いずれかの桁に3を含む正整数」だけではなく、smallerやjといったフラグに関する条件も含むことに注意してください。
[例えばj=1ならば、上からi桁目までに3を含む数しか数えてはいけません]

また、「上からi桁目までで」というのはかなり曖昧な表現なので、補足しておきます。
これは正確に言うと、「上からi桁目までを取り出したとき」という意味です。

例えば、12345という数を考えます。これの上からi=2桁目までを取り出した数とは、123のことです（一番左の桁を上から0桁目としています）。
従って、例えばN=12345のとき、

dp[3][0][0] = 0
dp[3][1][0] = 102
dp[3][0][1] = 1
dp[3][1][1] = 21

となります。これらの値は全て、先程の図から求めることができます。

また、上記の値の総和が124(=123以下の正整数の総数)であることも注目に値します。

###何を数えているか
i=(Nの桁数)のとき、dpが表す数値の意味は明らかでしょう。
例えば、N=12345のとき、問題の最終的な答えは、

dp[5][0][1] + dp[5][1][1]

となります。

しかし、i<(Nの桁数)の場合はどうでしょう。
このときのdpの値には、どんな意味があるでしょうか。これは、後々アルゴリズムを実装する段階で非常に重要になってくることです。

再び、先程のN=123の例に戻って考えましょう。先程の図をもう一度見てください。

図の四角で囲んだ部分を見てください。四角の中に含まれる数の総数が、dp[2][1][0]を表しています。
この数は、次にdp[3][smaller][j]を求める際に使われます。
例えば、dp[3][1][1]を求めるときには、四角の中の各値に対して一の位が3である数が一つずつ寄与するので、

dp[3][1][1] = dp[2][1][0] × 1 = 11

となります。

四角の中の一つ一つの数は、言うなれば「箱」を表していると考えることができます。条件により数を分類するための箱です。
それぞれの箱には条件が書かれていて、将来的に、箱の中には各々の条件を満たす数が入ります。
しかし、どの箱にいくつの数が入るかは、一の位まで調べてみないと分かりません。
その前に、十の位の段階でできることは、**「どの条件の箱がいくつあるか」**を予めカウントしておくことです。
そこで、それぞれの条件の箱の数を数えて、保持しておくための配列がdp[2]だというわけです。

dp[1]は、さらに一歩進んで「箱を入れる箱」だと解釈できます。
このように、配列dpは「箱」のカウンタ変数なのです。

###「寄与」の条件
dp[i]が、dp[i + 1]にどように寄与するかを考えます。
[通常は「寄与」ではなく「遷移」と言いますが、僕は「寄与」と言ったほうが分かりやすいと思うのでそうします]
未満フラグと3が出たかどうかのフラグは独立なので、別々に考えることにしましょう。

未満フラグ
以下、今調べている桁の数字をx、Nの上からi桁目をn[i]と書くことにします。

• smaller=0 から smaller=0 → x = n[i] のとき寄与
• smaller=0 から smaller=1 → x < n[i] のとき寄与
• smaller=1 から smaller=0 → 常に寄与なし
• smaller=1 から smaller=1 → 常に寄与

「既に3が出たか」フラグ

• j=0 から j=0 → x ≠ 3 のとき寄与
• j=0 から j=1 → x = 3 のとき寄与
• j=1 から j=0 → 常に寄与なし
• j=1 から j=1 → 常に寄与

#実装
###初期条件
桁DPが動作するには、初期条件が必要です。つまり、i=0のときのdpの値を手で設定しておく必要があります。

初期条件は、

dp[0][0][0] = 1
dp[0][0][1] = 0
dp[0][1][0] = 0
dp[0][1][1] = 0

となります。以下で、この理由を説明します。

まず、i=0とはどういう状況かを考えます。
上のdp配列の定義に戻ると、dp[0]というのは、

「上から-1桁目までで条件を満たす数の総数」

です。「-1桁目なんてないじゃないか」と思うかもしれません。しかし、こう考えてはどうでしょう。

N=12345とします。この上から0桁目は1です。-1桁目があるとすれば、その左隣です。そこには、0があるとは考えられないでしょうか。

i=-1桁目の数字は常に0である。こう考えると、先程の初期条件にも納得がいきます。
0以下の正整数は、0以外にありません。そして、それはNの-1桁目に一致しているので、smaller=0に属します。
また、-1桁目以前は全て0ですから、3は出てきていません。故に、0はj=0に属します。
こうして、smaller=j=0の場合だけ1、それ以外は0ということになります。

###寄与条件の書き方
実装のときは、上で書いた寄与の条件をそのままif文で書くこともできます。
しかし多くの場合、より簡潔で美しい（しかし少々テクニカルな）書き方があり、多くの人はそっちの書き方を好んで使います。
なので、ここでもその書き方を説明しておきます。

dp[i + 1][smaller || x < n[i]][j || x == 3] += dp[i][smaller][j];

変数の意味はこれまで用いてきたものと同じです。i, smaller, j, xについてはループを回していて、その中にこの式があります。

まず、最初に面食らうのが

[smaller || x < n[i]]

の部分でしょう。これは何なのか。場合分けをしてみると分かります。

• smaller=0 かつ x = n[i] の場合。このとき、上の[]の中身は0になります。これは、smaller=0 から smaller=0 への寄与に対応します。
• smaller=0 かつ x < n[i] の場合。このとき、上の[]の中身は1になります。これは、smaller=0 から smaller=1 への寄与に対応します。
• smaller=1 の場合。このとき、上の[]の中身は1になります。これは、smaller=1 から smaller=1 への寄与に対応します。
• smaller=1 から smaller=0 への寄与は存在しません。

フラグjについても同様です。

###コード
以上より、桁DPを実装したコードは次のようになります。

digit_dp.cpp

#include<cstdio>
#include<bits/stdc++.h>

using namespace std;

//Nは桁数が大きい場合があるので文字列として受け取る
string N;
vector<int> n;  //Nの各桁の数字を格納するベクター
int dp[100][2][2];

int main(){
  cin>>N;
  
  //ベクターnを構成
  for(auto a : N){
    n.push_back(a-'0');
  }
  int l = N.size();  //nの長さ

  dp[0][0][0] = 1;  //初期条件。他は0で初期化されている
  for(int i = 0; i < l; i++){
    for(int smaller = 0; smaller < 2; smaller++){
      for(int j = 0; j < 2; j++){
        for(int x = 0; x <= (smaller ? 9 : n[i]); x++){
          dp[i + 1][smaller || x < n[i]][j || x == 3] += dp[i][smaller][j];          
        }
      }
    }
  }

  cout << dp[l][0][1] + dp[l][1][1] << endl;
  
  return 0;
}

#最後に
こんな長い記事を読んで頂きありがとうございました！m(__)m