f:id:c_taquna:20200115005201p:plain

DPわからん！という人でも桁DPの基礎的な問題を解けるように型から学んでいきましょう。ちなみに、私もDPは苦手です。ちょうど先日に桁DPの勉強をして、基礎的な問題なら解けるようになったので、同じような人の助けになればいいなと思います。

本記事のテーマ

この記事は、下記問題が解けるようになることを目指しています。ちなみに、桁DPがどういったものかは改めて説明しません。

D - 禁止された数字

D - 1

E - Almost Everywhere Zero

S - Digit Sum

E - 数

コンセプトとしては、桁DPってわからない！という人でも実装パターンを学べば基礎的な問題を解けるようになることを目指しています。私自身、解答を見ないでも桁DPの基礎問題を解けるようになったので、誰かの参考になればと思います。

通常、理論→実践が普通の流れなのかと思いますが、理論を勉強してもいい感じに腹落ちしないのでこの際、実践→理論の流れで学ぶことで得られるものがあるんじゃないかなと考えています。

桁DPを使う場面

まず、どういった問題が出た時に桁DPで解けるか理解する必要があります。問題に下記のような表現があったら桁DPを疑ってください。

1以上 N以下の整数であって、と10 進法表記における〜〜という表現
制約に記載されている整数の桁数がすごく大きい(例：10¹⁰⁰⁰⁰)

上記に載せた問題のリンクはこの非負整数であることと10進法表記に関する記述が問題の中にあります。何度も言いますが、あくまでも基礎的な問題を解けるようにすることを目的としています。

参考にする問題

今回、下記問題を参考に説明していきます。 D - 1

問題の概要

1以上 N以下のすべての整数を十進表記で一回ずつ紙に書いた時、1という数字を何個書いたか求めよ

これを少し分解してみましょう。

1以上 N以下のすべての整数を十進表記
1という数字を何個書いたか
Nは最大10⁹

となります。まず、1と3は最初に書いた桁DPの問題表記パターンにマッチします。3の桁数についてですが、最低でも10⁹以上なんじゃないかなと思います。(AtCoderだと10⁸, 10⁹は全探索できない計算量なので)

なので、今回は桁DPでとくことができるんじゃないかなと推測がたてられます。

そして、2が今回の問題における問いとなり、これに対する解答を桁DPを使って求めていきます。

桁DPの実装パターン

ここからは、実装について解説していきます。

実装

今回、下記実装でACしています。なので、これをベースとして説明していきたいと思います。ポイントになるところには★をつけています。

static void Main(string[] args)
{
    string N = Console.ReadLine();
    int[,,] dp = new int[N.Length + 1, N.Length + 1, 2];
    dp[0, 0, 0] = 1;#★初期処理
    for (int i = 0; i < N.Length; i++)#★今みている桁
    {
        int nd = N[i] - '0';
        for (int j = 0; j < N.Length; j++) #★各問題における条件
        {
            for (int k = 0; k < 2; k++)#★他のサイトで未満フラグと呼ばれるもの
            {
                for (int d = 0; d < 10; d++)#★0 - 9の各値における処理
                {
                    int ni = i + 1;#★配るDPなので次のインデックス
                    int nj = j;
                    int nk = k;
                    if (d == 1) nj++;
                    if (k == 0)#★未満フラグが0だった時の処理
                    {
                        if (d > nd) continue;
                        if (d < nd) nk = 1;
                    }
                    dp[ni, nj, nk] += dp[i, j, k];
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= N.Length; i++)
    {
        res += (dp[N.Length, i, 0] + dp[N.Length, i, 1]) * i; #★答え
    }
    Console.WriteLine(res);
}

この構造を文字に起こすと下記のようになります。

インプットの入力

DPテーブルの定義と初期化

各桁を見るためのfor文

問題による条件を処理するためのfor文

未満フラグのfor文

0 - 9の値の時の処理を行うfor文

未満フラグによる場合分けのif文

DPテーブルの更新

解答の計算

ちょっと多いですが、慣れれば問題なく実装できるようになると思います。それぞれについて解説していきます。

1. インプットの入力, 2. DPテーブルの定義と初期化

インプットは特に特別なことをしていないので説明は割愛します。

ここで大切なのはDPテーブルの定義の仕方です。今回、属性が3つあります。これは、dp[i, j, k]とした時に下記の様に説明できます。

　i : 先頭からi桁目まで決められている

　j：先頭からi桁目まで決めた時に1がその数字に何個かかれているか

　k：未満フラグ ( k = 0 のとき、i桁目までNと一致している。k = 1 のとき、N よりも小さくなっている。ここがわからない場合は桁DPについて調べてみてください)

今回の問題特有の属性はjの部分なので、問題を解くときはここをどう処理するのか考える必要があります。これが難しいところだと思いますが、逆に実装の型を覚えておけば、ここが思いつけば勝てるので色々な問題を問いてパターンを覚えておくといいんじゃないかなと思います。

dp[0,0,0] = 1はなんでかわからないかもしれないですが、こういうものだと思ってください。

string N = Console.ReadLine();
int[,,] dp = new int[N.Length + 1, N.Length + 1, 2];
dp[0, 0, 0] = 1;

3. 各桁を見るためのfor文, 4. 問題による条件を処理するためのfor文, 5. 未満フラグのfor文, 6. 0 - 9の値の時の処理を行うfor文, 7. 未満フラグによる場合分けのif文, 8. DPテーブルの更新

タイトルの長さがやばいことになっていますが、この3 - 8 が桁DPのメイン部分です。

まず、基本となる考え方ですが、入力された値の各桁をみて、遷移を配るDPで実装していく感じです。まずは必要な部分だけを抜き出してみます。

for (int i = 0; i < N.Length; i++)
{
    int nd = N[i] - '0';
    for (int j = 0; j < N.Length; j++)
    {
        for (int k = 0; k < 2; k++)
        {
            for (int d = 0; d < 10; d++)
            {
                int ni = i + 1;
                int nj = j;
                int nk = k;
                if (k == 0)
                {
                    if (d > nd) continue;
                    if (d < nd) nk = 1;
                }
                dp[ni, nj, nk] += dp[i, j, k]
            }
        }
    }
}

これが定型パターンです。最初に説明しましたが、jは問題特有の属性なのでそこだけは都度考えてください。

まず、最初のfor文はndに今見ている桁の数値を入れます。
次のfor文はi桁目まで決まった時に1が何個あるかという情報を持つので、全桁を見て1があるかどうか判断する必要があるためレンジを0 <= j < N.Length としています。つまり、すべての桁を先頭から精査していく感じです。
3つ目のfor文は未満フラグです。これは2パターンしかないのでこの通りです
そして、大事なのは最後にある4つ目のfor文です。これは、各桁に対して、0-9の値をとった時の処理を記載しています。DPは遷移を考える必要があり、今回は配るDPのため、各桁の値が何であるかによってどの状態に遷移するのかここで決めます。

まず、次の状態を表す ni を定義します。nj, nk はデフォルトで同じ状態に遷移するようにj, k の値で初期化をします。

if文ですが、k == 0 で処理に入っているのですが、これは今処理している桁の値がNの同じ桁の値と比較したときにどんな関係を持つかによって、次の状態がかわるため必要になります。

そして、最後は次の状態に今の状態がもつ値を足していくことでDPテーブルが完成します。

ただ、これだけだとまだ解答にはなりません。今回の問題特有の処理を入れる必要があります。それが下記です。

if (d == 1) nj++;

これが何をしているのかというと簡単で、各桁の値を0 - 9と比較している時に、1の時にnjをインクリメントしています。こうすることで、遷移先がdp[i+1, j + 1, k ]となります。j はもとから1の数を表す属性だったので問題なさそうです。

9. 解答の計算

最後に、問いに対しての解答を作成する必要があります。

ここも少し気をつけなければならないのが、何を求めるのか、テーブルのどの値を持ってくればいいのか考えなければならないという点です。もちろんテーブルは問題によって異なるのでここも自分で考えます。

今回、j の値が1が書かれている数に関することなのですべてのパターンについて総和をとります。

まとめ

とりあえず困ったときは、下記の型を作りましょう。その上で、問題にそった情報を実装してあげると解答できるんじゃないかなと。

for (int i = 0; i < N.Length; i++)
{
    int nd = N[i] - '0';
    for (int j = 0; j < N.Length; j++)
    {
        for (int k = 0; k < 2; k++)
        {
            for (int d = 0; d < 10; d++)
            {
                int ni = i + 1;
                int nj = j;
                int nk = k;
                if (k == 0)
                {
                    if (d > nd) continue;
                    if (d < nd) nk = 1;
                }
                dp[ni, nj, nk] += dp[i, j, k]
            }
        }
    }
}

例題の解き方も書こうと考えましたが、完全に力尽きたのでここまでにしておきます。。

たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【C#】型から入る桁DP