SRM510 Div1Easy TheAlmostLuckyNumbersDivOne(再)

SRM 練習会

http://community.topcoder.com/stat?c=problem_statement&pm=11461

昨日のskypeのあと、桁DPについてなんとなく理解したので演習用に再挑戦。実装において参考にしたのは以下のページです。（特に遷移について詳しく書かれていたのが良かったです。ありがとうございます）
torus711.hatenablog.com

今回の場合、状態は
dp[見ている桁][n以下が確定][4と7以外の個数][頭が0か否か]
の4つとします。4つ目の条件がやや特殊ですが、これがないと一部の数え上げがうまくいきません。

ex.) 12345以下について数え上げる場合
例えば、"707"は明らかにAlmostLuckyNumberです。しかしこのDPにおいて"707"は"00707"と認識されるため、4or7以外が3つ("00-0-")使われたもの、すなわちAlmostLuckyNumberでないとみなされることになります。これを回避するには、頭の"00"を4or7以外の数としてカウントしなければいいわけなので、簡単なフラグを利用します。

i:=0/1=数えたい数字の最上位が0/else、を設定して"00707"をDP風に解釈すると
"0????"(i=0)→"00???"(i=0)→"007??"(i=1)→"0070?"(i=1)→"00707"(i=1)
となっていい感じに頭の"00"を無視できます。あとはこれを書き下すだけです。


初歩的な話かもしれないですけど、多くの桁DP（いうほど見てない）でdp[0][0]…[0]=1として上手くいく理由がわかりません。直感に反するというか、dp[0][0]…[0]に対する場合の数は定義できない気がして。今回だって、0桁目を見ていてn以下が確定していなくて4と7以外の個数が0個で頭が0の数ってなんだよっていう。*1

#include <bits/stdc++.h>
using namespace std;

class TheAlmostLuckyNumbersDivOne {
public:
    long long count(string s){
        int n=s.size();
        // 桁/確定/4.7以外個数/頭0,頭0以外
        long long dp[20][2][20][2]={};
        dp[0][0][0][0]=1;
        for(int i=1;i<=n;i++){
            int num=s[i-1]-'0';
            for(int j=0;j<2;j++){
                for(int d=0;d<=(j?9:num);d++){
                    for(int k=0;k<20;k++){
                        for(int l=0;l<2;l++){
                            if(d==0&&l==0) dp[i][j||d<num][k][l||d!=0]+=dp[i-1][j][k][l];
                            else dp[i][j||d<num][k+(d!=4&&d!=7)][l||d!=0]+=dp[i-1][j][k][l];
                        }
                    }
                }
            }
        }
        long long ret=0;
        for(int j=0;j<2;j++)for(int k=0;k<2;k++){
            ret+=dp[n][j][k][1];
        }
        return ret;
    }

    long long find( long long a, long long b ) {
       string A=to_string(a-1);
       string B=to_string(b);
       return count(B)-count(A);
    }
};

*1:追記：ここのコメント欄が答えっぽいけどモヤモヤが取れない。 桁DP入門 - pekempeyのブログ