ABC 029

Table of Contents

https://atcoder.jp/contests/abc029

A. 複数形

https://atcoder.jp/contests/abc029/tasks/abc029_a

B. カキ

https://atcoder.jp/contests/abc029/tasks/abc029_b

C. Brute-force Attack

https://atcoder.jp/contests/abc029/tasks/abc029_c

D. 1

https://atcoder.jp/contests/abc029/tasks/abc029_d

自力 AC だが桁 DP の問題ということをわかった上で解いた。

dp[i][is_less][c] を上位 $i$ 桁目までの数を見て $N$ 以下であることが確定(している is_less=1, していない is_less=0)かつ 1 の個数が c 個であるような数の個数とする。 dp[0][0][0] = 1 として、桁を進めていく。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    cin >> N;

    int sz = N.size();

    int mx = 15;
    vector dp(sz + 1, vector(2, vector<mint>(mx)));
    dp[0][0][0] = 1;

    rep2(i, 1, sz + 1) {
        int t = N[i - 1] - '0';
        rep(d, 10) {
            bool is_one = d == 1;
            rep(c, mx) {
                if (d < t) {
                    dp[i][1][c + is_one] += dp[i - 1][0][c];
                }
                if (d == t) {
                    dp[i][0][c + is_one] += dp[i - 1][0][c];
                }
                dp[i][1][c + is_one] += dp[i - 1][1][c];
            }
        }
    }

    mint ans = 0;
    rep2(c, 1, mx) {  // (N 未満の数で 1 の個数が c 個である数の個数) * c
        ans += dp[sz][1][c] * c;
    }
    for (char c : N) {  // N そのものの 1 の個数を数える
        if (c == '1') ans++;
    }
    cout << ans.val() << endl;
}