AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の82問目である「Counting Numbers（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【082 – Counting Numbers（★3）】
問題文
何も書かれていない黒板があります。x=L, L+1, …, R の順に、以下の操作を行います。
- 黒板に、整数 \(x\) を\(x\)回書く。
- 全ての操作が終了した後、黒板に書かれている文字の個数を \(10^9 + 7\) で割った余りを求めてください。
ただし、数えるのは整数ではなく文字であることに注意してください。例えば、整数 15 は 2 個の文字として数えます。
考察
考えた内容の概要
与えられた範囲 L から R までの全ての整数を黒板に書く際、黒板に書かれる文字の総数を求める問題を考えます。ここで、文字の総数とは、各整数を構成する数字の個数の合計です。
考えたことの内容
まず、L から R までの各整数を順に考え、それぞれの整数が何桁かを確認します。次に、各桁数における整数の個数を求め、その桁数分だけ文字数が増加することを考慮します。これを全ての桁数について行い、合計することで答えを求めます。
実装した内容
L と R の桁数 min_len と max_len を求めます。min_len から max_len までの各桁数について、以下の処理を行います。
- 現在の桁数における L と R の範囲を求めます。
- その範囲にある整数の個数を求めます。
- その範囲にある整数を全て書いたときの文字数を加算します。
- 最後に答えを出力します。
コード
# 入力を受け取る
L, R = map(int, input().split())
# 定数として 10^9 + 7 を設定
mod = 10**9 + 7
# L と R の桁数を求める
min_len = len(str(L))
max_len = len(str(R))
# 答えを初期化
ans = 0
# 各桁数について考慮する
for dig in range(min_len, max_len + 1):
# 現在の桁数における L と R の範囲を求める
t_left = max(10**(dig - 1), L)
t_right = min(10**dig - 1, R)
# t_left と t_right の間にある整数の個数を求める
between_num = t_right - t_left + 1
# 現在の桁数における必要な文字数を加算する
ans += between_num * (t_left + t_right) // 2 * dig
# 答えを mod で割る
ans %= mod
# 答えを出力する
print(ans)解説
min_lenとmax_lenは、それぞれ L と R の桁数です。t_leftとt_rightは、考慮している桁数における L と R の範囲です。between_numは、t_leftとt_rightの間にある整数の個数です。ansには、各桁数における必要な文字数を加算していきます。- このようにして、桁数ごとに計算を行い、最終的な答えを出力します。
コメント