ABC 154
Table of Contents
https://atcoder.jp/contests/abc154
A. Remaining Balls
https://atcoder.jp/contests/abc154/tasks/abc154_a
B. I miss you
https://atcoder.jp/contests/abc154/tasks/abc154_b
C. Distinct or Not
https://atcoder.jp/contests/abc154/tasks/abc154_c
D. Dice in Line
https://atcoder.jp/contests/abc154/tasks/abc154_d
E. Almost Everywhere Zero
https://atcoder.jp/contests/abc154/tasks/abc154_e
自力 AC. 桁 DP の問題だということをわかった上で解いた。
dp[i][is_less][c] を上位 $i$ 桁目まで見ていて、$N$ よりも小さいことが確定しているフラグ is_less と、0 以外の数字の個数 c を持つ DP 配列を定義する。
dp 配列を更新する際、$0$ 以外の数が $K+1$ となるケースは興味ないので全て $K+1$ に丸めておく。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string N;
ll K;
cin >> N >> K;
int M = N.size();
vector dp(M + 1, vector(2, vll(K + 2)));
dp[0][0][0] = 1;
rep2(i, 1, M + 1) {
int t = N[i - 1] - '0';
rep(d, 10) {
int is_not_zero = d != 0;
rep(c, 4) {
int nxc = min(c + is_not_zero, K + 1);
if (d < t) {
dp[i][1][nxc] += dp[i - 1][0][c];
}
if (d == t) {
dp[i][0][nxc] += dp[i - 1][0][c];
}
dp[i][1][nxc] += dp[i - 1][1][c];
}
}
}
ll ans = dp[M][1][K] + dp[M][0][K];
cout << ans << endl;
}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S;
ll K;
cin >> S >> K;
ll N = S.size();
vector dp(2, vll(K + 2));
dp[0][0] = 1;
rep(i, N) {
int t = S[i] - '0';
vector dpn(2, vll(K + 2));
rep(d, 10) rep(is_less, 2) rep(num_non_zero, K + 1) {
if (!is_less && d > t) continue;
int non_zero = d != 0;
int is_less_n = is_less || d < t;
dpn[is_less_n][num_non_zero + non_zero] += dp[is_less][num_non_zero];
}
swap(dp, dpn);
}
cout << dp[0][K] + dp[1][K] << endl;
}