Atcoder ABC #029 D. 1

D: 1 - AtCoder Beginner Contest 029 | AtCoder

1からnまでの数字を全て書いた時、1が何回現れるかを求める問題。例えばn=15なら8と答える。

部分点のn <= 999のときは、とりあえず愚直に数えるだけなので、あとで満点解法のデバッグができるようにてきとうに書いておいた。さて、n<=10^9のときは当然間に合わないので、考察する。ある桁に1が現れる数の個数ではなく、１そのものの個数を求めるので、各桁について、その桁の数を１に固定したときに作ることができる数の総数を独立に求めればよい。まず各桁について、その数字が２以上９以下だったときの処理は意外と簡単であることに気付く。例えば、n=2185だとして、10の位の8に注目しているとする。これを1に書き換える操作を考えると、〇〇1○という数字であって、2185以下のものを数えれば、この位置が1であるものはすべて網羅することができる。このとき、最初の２つの数字は、00から21のすべてを動き、8は1より大きいので残りの1桁は自由に選んで構わない。よって、この場合、(21 + 1) * 10 = 220と求めることができる。注目している数が1のときは、例えば上の例でいうと、最初の左の数は、0または1にしたときは下2桁は自由に選んで良い。2にしたときは、下2桁は86種類とりうるので、2 * 100 + 86と求められる。0のときも同じように考える。先頭と末尾は注意して処理する必要がある(11などをうまく処理できるように）。

#include "bits/stdc++.h"
using namespace std;

int main() {
        int i, j;
        string s;
        cin >> s;
        int n = s.size();
        int ans = 0;
        for (i = 0; i < n; i ++) {
                if (s[i] == '0' || s[i] == '1') {
                        if (i != 0) {
                                string first = s.substr(0, i);
                                int res = stoi(first);
                                for (j = 0; j < n - i - 1; j ++) res *= 10;
                                ans += res;
                        }
                        if (s[i] == '1') {
                                if (i != n - 1) {
                                        string last = s.substr(i + 1, n - i - 1);
                                        ans += stoi(last);
                                }
                                ans ++;
                        }
                } else {
                        if (i != 0) {
                                string first = s.substr(0, i);
                                int res = stoi(first) + 1;
                                for (j = 0; j < n - i - 1; j ++) res *= 10;
                                ans += res;
                        } else {
                                int res = 1;
                                for (j = 0; j < n - 1; j ++) res *= 10;
                                ans += res;
                        }
                }
        }
        cout << ans << endl;
        return 0;
}

なんか桁DPとかいうものを使って解くのがいいらしいけど、それが何かはまだ知らない。