082 - Counting Numbers（★3）

[hxrxchang]

https://atcoder.jp/contests/typical90/tasks/typical90_cd

問題概要

LからRまでの数字をiをi回黒板に書いていく。黒板に書かれた文字数はいくつか？ L R が 3 5 の場合、333444455555 となるので答えは12文字。

解法

L, Rは最大10 ** 18なので、L~Rの数字を1つずつ計算していくのは無理。

そこで、Lの桁数からRの桁数までを1桁ごと考えていくと、最大18回のループで済む。

• 1~9, 10 ~ 99, 100~999 ... の数字の集合と LからRの数字の集合の積集合を求める。
• ↑で求めた積集合を、等差数列の和の公式を使って和を求めて、桁数を掛けると文字数を求めることができる。
  • 入力例2の 98 100 だったら、桁数2の10~99 には 98, 99 がある。
  • 初項98、 末項99、 項数2の等差数列の和は、2 * (98 + 99) // 2 であり、これで数字を何回書いたかが分かる。
  • 文字数を求めるには、書いた数字回数に桁数を掛ければいい。
• これをRの桁数まで繰り返す。

MOD = 10 ** 9 + 7
L, R = map(int, input().split())

# Lの桁数
l_digit = len(str(L))
# Rの桁数
r_digit = len(str(R))

ans = 0
# Lの桁数からRの桁数まで各桁を考える
for i in range(l_digit, r_digit + 1):
    # 例えばi=1のとき、min_numは Lまたは1のどちらか大きい方、max_numは Rまたは9のどちらか小さい方になる
    min_num = max(L, 10 ** (i - 1))
    max_num = min(R, 10 ** i - 1)

    num = max_num - min_num + 1

    # 初項、末項、項数が分かるときの等差数列の和の公式を使って、min_numからmax_numまでの和を求める
    # 桁数でかけるかけることで、文字の個数を求める
    ans += (num * (min_num + max_num) // 2) * i
    ans %= MOD

print(ans)

https://atcoder.jp/contests/typical90/submissions/52123558