Pythonで毎日AtCoder #51

はじめに

前回

#51

問題

考えたこと
本番では、$i,j$を全探索してTLEしました。計算量は$O((2*10^5)^{2})$となります。この問題の制約だと、$O(N)$くらいに抑えないと通りません。

十進数で表記されている数字は$a_i*10^n+a_{i-1}*10^{n-1} \cdots a_0 * 10^0$と表すことができます。長さ$N$の文字列$S$を右から$i$番目で分けたときの文字列を$S_i$とすると$S_i$は$S_0 + S_1 * 10 ^ 1 \cdots S_i * 10 ^ {N-i}$と表せます。飛び飛びで文字を分けて結合することはできないので、$S$の$i,j,i<j$の区間の文字列$S_{i-j}$は$S_{i-j} = \frac{S_{j}-S_{i}}{10^i}$と書けます。ここで、$2019,10^i$は互いに素(最大公約数が1)です。よって、$S_{i-j}$が2019の倍数であるかの判定は前の式の分母($\frac{S_{j}-S_{i}}{10^i}$)が2019の倍数であることの判定と同値です。また、2019で割った余りが同じ異なる2数どうしを引き算すれば2019で割り切れる数になります。ですので、それぞれ$i$の$S_{i} mod(2019)$を記録します。私は、余りを記録するlistを作る時に躓きました。2019で割った余り$m$は当然$0 \leq m < 2019$になりますが、余り0の時だけは$S_i$だけで2019の倍数になれます。なので、余りを記録するlistの余り0の項は最初に+1しておきます。この+1は長さ0の文字列があって、余り0のときは長さ0の文字列とペア→単体で2019の倍数となるような気持ちです。組み合わせを計算する式は、${}_n C _2$を変形して$n*(n-1)$となります。

s = input()

t, a = 0, 1
mod = [0]*2019
mod[0] = 1 #最初の要素(余り0)は+1
s = s[::-1] #後ろから調べた方が位取りしやすいのでreverse
n = len(s)
for i in range(n):
    t += int(s[i]) * a
    t %= 2019
    a *= 10
    a %= 2019 #互いに素なので%2019を計算しても答えtは変わらない
    mod[t] += 1
ans = 0

for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2 #組み合わせの計算
print(ans)

t, a = 0, 1って別の行に書いたほうがいい? PEP8で探せなった。

まとめ

本番に解きたかった。今週は最高に幸せなことにABCが二回あるので入茶します。ではまた。