読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

D問題: 1 - AtCoder Beginner Contest 029

プロコン

Sat Sep 19 20:44:59 JST 2015

ABC 029 - D問題

問題: n が与えられる. 10進数で 1 から n を並べて記述したとき、1 という桁はいくつ出現するか

解答

naiiveデバッグのための素朴な解法. 結果的にこれを部分的に用いる solve で通した.

int naiive(int m, int n) {
  stringstream ss;
  for (int i=m;i<=n;++i) ss << i;
  string s(ss.str());
  int ans = 0;
  for (char c: s) if (c == '1') ++ans;
  return ans;
}

/*
 * 1 .. n
 * を
 * [0..9], [10..19], [20..29], ...
 * にグルーピングして考える
 */
int solve(int n) {
  if (n < 100) return naiive(1, n);
  int ans = 0;
  int k = 1;
  while (n > 0) {
    int m = (n/10) * 10;
    if (m <= n) ans += naiive(m, n) * k;
    ans += (m/10) * k;
    n = (m/10) - 1;
    k *= 10;
  }
  return ans;
}