AtCoder Beginner Contest 029 D - 1

1 位の人 4 分弱で解いてますが早すぎでしょさすがに…

問題

abc029.contest.atcoder.jp

解法

桁 DP で解きました。

dp[keta][num][sf] = (keta 目の桁を見ている時点ですでに num 個の 1 を持っていて, N より小さいというフラグが sf であるような数字の個数) という dp を上手いこと処理します。

ll dp[12][12][2]; // keta, 1's num, small flag
ll p10[12];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    p10[0] = 1;
    for (int i = 1; i < 12; i++) p10[i] = p10[i-1] * 10;
    dp[11][0][0] = 1;
    for (int keta = 11; keta > 0; keta--) {
        for (int n1 = 0; n1 < 12; n1++) {
            for (int sf = 0; sf < 2; sf++) {
                if (sf == 0) {
                    int maxi = (N / p10[keta-1]) % 10;
                    for (int i = 0; i < maxi; i++) {
                        if (i == 1) {
                            dp[keta-1][n1+1][1] += dp[keta][n1][sf];
                        } else {
                            dp[keta-1][n1][1] += dp[keta][n1][sf];
                        }
                    }
                    if (maxi == 1) {
                        dp[keta-1][n1+1][0] += dp[keta][n1][sf];
                    } else {
                        dp[keta-1][n1][0] += dp[keta][n1][sf];
                    }
                } else {
                    for (int i = 0; i < 10; i++) {
                        if (i == 1) {
                            dp[keta-1][n1+1][1] += dp[keta][n1][sf];
                        } else {
                            dp[keta-1][n1][1] += dp[keta][n1][sf];
                        }
                    }
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < 12; i++) for (int j = 0; j < 2; j++) {
        ans += i * dp[0][i][j];
    }
    cout << ans << endl;
    return 0;
}