TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$lowerBound \sim upperBound$までの数の桁の和を求める．$x$未満の桁の数の和を$f(x)$として$f(upperBound + 1) - $ $f(lowerBound)$を出す．とりあえず並べて書いてみた．

$$ 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ = 45 \\ 10\ 11\ 12\ 13\ 14\ 15\ 16\ 17\ 18\ 19\ = 45 + 10\\ 20\ 21\ 22\ 23\ 24\ 25\ 26\ 27\ 28\ 29\ = 45 + 20\\ …\\ 90\ 91\ 92\ 93\ 94\ 95\ 96\ 97\ 98\ 99\ = 45 + 90\\ $$

となり，$1$桁の数の先頭に数字がついたと考えると$45 \times 10 + (10 + 20 + … + 90)$と考えられる．これはくくると$10 \times (45 + 45)$となる．$10, 100, 1000$未満を考えると次のようになる

$$ \begin{eqnarray} f(10) &=& (0+1+..+9) \\ f(100) &=& 10 \times ((0+1+..+9) + (0+1+..+9)) \\ f(1000) &=& 100 \times ((0+1+..+9) + (0+1+..+9) + (0+1+..+9)) \end{eqnarray} $$

次に適当な$4$桁の数字，$5832$で考える．この数を左から$5\textcolor{red}{832}$，$8\textcolor{red}{32}$，$3\textcolor{red}{2}$, $2$と見る．それぞれ黒の数字が今見ている桁で，例えば最初の例を考えると$5000$以降，$5$は後$832$回呼ばれる．$5000$未満の数は$000 \sim 999$の先頭に$0 \sim 4$までをつけたと考えると $$ f(5000) = 0\\ f(5000) += 0 \times 1000 + f(1000)\\ f(5000) += 1 \times 1000 + f(1000)\\ f(5000) += 2 \times 1000 + f(1000)\\ f(5000) += 3 \times 1000 + f(1000)\\ f(5000) += 4 \times 1000 + f(1000) $$

と計算出来る．サンプルが強い．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

vector<int> ch(ll x) {
  vector<int> ret;
  while(x) {
      ret.push_back(x % 10);
      x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}

ll f(ll x) {
  if(x <= 0) return 0;
  vector<int> v = ch(x);
  vector<int> t(v.size());
  ll tt = 1;
  rep(i, v.size()) {
      t.push_back(tt);
      tt *= 10;
  }
  reverse(t.begin(), t.end());
  t.push_back(0);

  ll ret = 0;
  rep(i, v.size()) {

      ll a = (v.size() - 1 - i) * 45;
      rep(j, v[i]) {
          ret += j * t[i];
          ret += a * t[i+1];
      }

      x -= t[i] * v[i];
      // cout << v[i] << " " << t[i] << " " << x << " " << a << " " << a * t[i+1] << endl;
      ret += x * v[i];
  }

  return ret;
}

class SumThemAll {
  public:
  long long getSum(int lowerBound, int upperBound) {
      return f(upperBound+1) - f(lowerBound);
  }
};