競プロ典型 90 問：082 - Counting Numbers（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/11/03
• 結果：解けた
• 時間：2時間ぐらい

考えたこと

• i桁の整数単位で計算すれば良さそう
• 解法は5分ぐらいで思いついたけど、実装やデバッグがうまく行かなかった・・・。

公式解説

https://twitter.com/e869120/status/1411094412319330305/photo/1

解説を読んだふりかえり

• 大方針としての考え方はあっていた。
• 実装に苦労したのは、下記のような考え方に気が付かなかったからか。。。
  • 
  • 
• 一応解けたけど、これは後日もう一度やってみよう。

ソース

L,R = [int(x) for x in input().split()]
MOD = 10**9 + 7

ans = 0
# 各桁(i桁)で集計する。
for i in range(1, 20):
    # a～bの個数を後で計算する。
    # LやRが関係しなければ、a=10**(i-1), b=(10**i)-1。
    isCalc = False
    if L <= 10**(i-1) and (10**i)-1 <= R:
        a,b = 10**(i-1), (10**i)-1
        isCalc = True
    elif 10**(i-1) <= L and  R < 10**i:
        a,b = L,R
        isCalc = True
    elif 10**(i-1) <= L < 10**i:
        a,b = L, (10**i)-1
        isCalc = True
    elif 10**(i-1) <= R < 10**i:
        a,b = 10**(i-1), R
        isCalc = True
    # a～bについて計算。i桁なのでiをかける。
    if isCalc:
        sub = (a+b) * (b-a+1) //2
        ans += sub * i
        ans %= MOD

print(ans)