yukicoder No.220 世界のなんとか2

問題

問題概要

桁dpの問題

解法

dp[i][j][k][l]という配列を作りdpで埋めていく感じ。
整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。 k=1の時はすでにi番目までに数字3を含んでいて、k=0の時は含まれていない。 lはi番目の桁まで考えた時のmod3の値を示している。 このような情報でdpができるのは、新しく追加する数字は２通りの方法の場合分けで決めることができるから。
例えば、p=2のとき100以下の数で考えるとする。
(1)1桁目に1を選んだとき, (2)1桁目に0を選んだときで場合分けができる。
(1)の時、2桁目に入れることができるのは、0のみ。(2)の時、2桁目に入れられるのは0~9のどの数字でも入れることが可能である。 どうしてこのようになるかは(1)のときは、まだ100より小さな数字になることが決まっておらず、100以下にすることが可能であるという状況なので、2桁目は100の2桁目の0以下の数字を選ばなければならない。一方で、(2)のときは、すでに1桁目が0であることからすでに100未満の数字しか作ることができないので、0~9のどの数字を入れてもよい。
だからこの未満と以下のどちらであるのかの情報と、3を含んでいるのかと3の倍数であるのかの情報を持っておけばいい。3を含んでいるかは3を使ったかどうかだけを見ればよく、3の倍数判定はすべての桁の和が3の倍数であればその数も3の倍数となるので、和をmod3したもので判定できる。
以下のサイトが桁dpについてとてもわかりやすい解説をしています。

pekempey.hatenablog.com

ミス

桁dpをしっかりとくのは初めて。

コード

#include <iostream>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[i][j][k][l]
//整数pを考えた時に、i番目の桁まで考えて、j=1の時は考えている数がp未満であることが決定していて、j=0の時はp以下である。
//k=1の時はすでにi番目までに数字3を含んでいて、k=0の時は含まれていない。 lはi番目の桁まで考えた時のmod3の値
long long dp[30][2][2][3];

int main(void){
    int p; cin >> p;
    dp[0][0][0][0] = 1;
    rep(i, p + 1){
        rep(j, 2){

            int lim;
            if(j == 1) lim = 9;//i桁目までですでに未満が決まっていればi+1桁目の数字は何でもよい
            else if(j == 0 && i == 0) lim = 1;//未満が決まっていなくても１ケタ目には１を入れる場合がある
            else lim = 0;//未満が決まっていなければ0しか入れられない
            
            rep(k, 2){
                rep(l, 3){
                    rep(m, lim + 1){
                        dp[i + 1][j || m < lim][k || m == 3][(l + m) % 3] += dp[i][j][k][l];
                    }
                }
            }
        }
    }

    long long ans = 0;
    rep(j, 2) rep(k, 2) rep(l, 3){
        if(k == 1|| l == 0){//３が含まれているまたは３の倍数
            ans += dp[p + 1][j][k][l];
        }
    }
    cout << ans - 1 << endl;//0も含んで考えてしまっているので、   -1
    return 0;
}