AtCoder Beginner Contest 029 D - 1
1 位の人 4 分弱で解いてますが早すぎでしょさすがに…
解法
桁 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; }