ABC238C

ABC238C の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc238/submissions/29083168

問題

少し条件が入った数列の総和の問題です．
f(x)は，x以下の正整数で，xと桁数が同じものの数を表すとき，
与えられた整数Nについて，
f(1)からf(N)の総和を求めます．

例えば f(16)は，16以下の正整数
[1, 2, ,3, ..., 9, 10, 11, 12, 13, 14, 15, 16]
のうち，16と桁数が同じものは，
[10, 11, 12, 13, 14, 15, 16]
の7つですので，
f(16) = 7
となります．

解説

Nが10^18のオーダーですので，単純なループで総和を求めることは不可能です．

そこで，規則性について理解するために，例としてN=16の時の場合を，手を動かして考えます．

ABC238C_ex1

上図のように考えると，10から16についての和を考えるとき，9を7回引いてあげれば良いことがわかります．

では，次の例を見てみます．

ABC238C_ex2

このように，99ないしは，9のように小さい桁の数字の分だけあとから引いてあげれば良いです．

コードにします．

標準入力を読み込みと，MODを定義します．

N = int(input())
MOD = 998244353

まず，1からNまでの総和を計算します．

x = N*(N+1)//2

ここから，9999, 999, 99, 9のような数字を個数分だけ引いていきます．for分の最初のループだけ，139個=238-99 のように，9000個，900個，90個，9個のようなキリのいい数字にはならない点に注意してください．

l = len(str(N))
for i in range(l-1, 0, -1):
    y = 10**i - 1
    if i == l-1:
        num = N - y
    else:
        num = 9 * 10**i
    x = x - num*y

最後にMODを計算して，出力します．

print(x % MOD)

以上，ABC238Cの解法でした．

＜参考解説リンク＞

1) 【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する！ - Qiita