ABC029 D問題 1

久しぶりに暇だったのでやってみた。
桁DPなるものを初めてやったのでメモ

digitDPはこのサイトが驚くほどわかりやすいtatanaideyo.hatenablog.com

考え方はいわゆるdigitDP
dpの配列を、dp[何桁目を見ているか][今見ている桁までで1が何回出ているか(桁の数以下)][その数はNより小さいか]というようにとる。
何桁目を見ているかは、0桁目をlen(N)+1桁目の仮想的なものとし、上から1,2桁と数える。
1が何回出ているか、というのをまとめるところに今回の数をまとめるdp要素がある。
その数より小さいかは、0ならギリギリ、1なら余裕を表す。
あとはdpを回すだけ。

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    string sN = to_string(N);

    //digitDP
    // keta, 1num, is smaller than N
    int dp[11][11][2];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    for(int keta=1; keta<=len(sN); keta++){
        for(int num=0; num<11; num++){
            for(int is=0; is<2; is++){
                if(is == 0){ //no
                    int mx = sN[keta-1]-'0';
                    for(int i=0; i<mx; i++){
                        if(i == 1){
                            dp[keta][num+1][1] += dp[keta-1][num][is];
                        }else{
                            dp[keta][num][1] += dp[keta-1][num][is];
                        }
                    }
                    if(mx == 1){
                        dp[keta][num+1][is] += dp[keta-1][num][is];
                    }else{
                        dp[keta][num][is] += dp[keta-1][num][is];
                    }
                }else if(is == 1){ //ok
                    for(int i=0; i<10; i++){
                        if(i == 1){
                            dp[keta][num+1][is] += dp[keta-1][num][is];
                        }else{
                            dp[keta][num][is] += dp[keta-1][num][is];
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i=0; i<11; i++){
        for(int j=0; j<2; j++){
            res += i*dp[len(sN)][i][j];
        }
    }
    cout << res << endl;
}