ABC195 C問題のお粗末な解き方

ABC195のC問題を解説しつつ、ふりかえります。

atcoder.jp

数字に3桁ずつコンマをうちます。例えば 10000 なら 10,000。
数字Nが与えられて、1〜Nまででコンマの数の合計を求める問題です。

ちなみに私の解き方は公式解説の解き方よりまわりくどい解き方です。
公式解説のようにコンマのうたれる位置に着目した解き方の方がスッキリすると思います。

まずNの最大値は 10^{15}で余裕で億を超えてくる値なので、何かしら工夫が必要なことがわかります。

桁数からコンマの数を求めることを考えました。
4桁〜6桁の時にコンマの数は1
7桁〜9桁の時にコンマの数は2
という感じで、桁数をkとすると >|python|(k - 1) // 3||< で求められます。

次に桁数に応じて数字の個数を求めました。
例えば、
3桁の数字の範囲は100〜999なので、個数は 999 - 100 + 1 = 900個です。
4桁の数字の範囲1000〜9999なので、個数は 9999 - 1000 + 1 = 9000個です。
同様に
15桁の数字の範囲は 10^{14}〜10^{15} - 1なので、個数は 9 * 10^{14}です。

解き方のイメージ
解き方のイメージ

これはあらかじめ求めて配列に保存しておきます。

keta_mat = [0 for _ in range(17)]
# マックス桁数とその数の個数
for i in range(1, 17):
    keta_mat[i] = 9 * (10 ** (i - 1))

次にNの桁数とその桁数の個数を求めて、k桁だったときのコンマの数とその桁数の個数を求めます。
例えば、N = 31431だったら、桁数は5桁。1〜31431までで、5桁の数字の個数は、 31431 - 10^4 + 1 = 21432
あとは4桁の数字の個数と4桁の時のコンマの数を足せば、答えになります。

もう少し一般化すると、k桁の数字だったら、k桁の数字の個数 * k桁のコンマ数 + k-1桁の数字の個数 * (k-1)桁のコンマの数という風に、足していきます。

全体のコードはこんな感じになりました。

from math import log10
N = int(input())

keta_mat = [0 for _ in range(17)]

# 桁数と桁数ごとの個数
for i in range(1, 17):
    keta_mat[i] = 9 * (10 ** (i - 1))

# Nの桁数
max_k = int(log10(N)) + 1

# max_k桁 の個数
max_keta_num = N - 10 ** (max_k - 1) + 1

ans = ((max_k - 1) // 3) * max_keta_num

for i in range(max_k - 1, 0, -1):
    ans += ((i - 1) // 3) * keta_mat[i]

print(ans)

公式解説のようにコンマのうたれる位置ごとに数え上げた方がシンプルです。
積み上げて数えるイメージが足りなかったと思います。
お粗末な解き方でした。