ABC164

AtCorder Beginner Contest 164 に参加しました。
ABCの3問ACでした。
Pythonを使用しています。

A問題

狼Wが羊S以上のときに、羊は狼に襲われてしまうのでunsafeです。

S, W = map(int,input().split()
if S <= W:
    print("unsafe")
else:
    print("safe")

B問題

高橋君の体力0になるのに必要なターン数をt、青木君の体力が0になるのに必要なターン数をaとします。
高橋君が勝つのは、青木君の体力が先に0になるときなのでtがaよりも大きいときです。
さらに体力0になるのに同じターンかかる場合でも、先攻の高橋君の勝利です。

A, B, C, D = map(int,input().split())
import math
t = math.ceil(A / D)
a = math.ceil(C / B)
if t >= a:
    print("Yes")
else:
    print("No")

C問題

得られた景品をリストSに格納します。
重複を除いたリストを作成し、要素数を求めます。

N = int(input())
S =[input() for i in range(N)]
import collections
c = collections.Counter(S)
print(len(c))

D問題

1~200000の間にある2019の倍数を全て求め、リストbaisuuに入れます。
2019を含んでいるか→4038を含んでいるかのように順番に探索していきます。
しかし、18171(=2019*9)のように先頭と最後に同じ数を含んでいる場合、181718171に18171が2個含まれていることを確認できませんでした。

S = input()
import re
baisuu = [2019 * i for i in range(200000 // 2019)]
count = [len(re.findall(str(i), str(S)))
         for i in baisuu if str(i) in str(S)]

2019の倍数ということは2019で割ったあまりが0であるということです。
範囲指定の際に両方を動かすのではなく、右端に固定して考えることで計算量が少なくなります。

適当な具体例としてS = 12114が2019で割り切れえるか考えます。
右端を固定し左端を1つずつずらしながら余りを求めます。
1 → 1
41 → 41
141 → 141
1141 → 1141
21141 → 951
121141 → 1
余りが一致するのは、1桁のときと6桁のときです。
これは、6桁目~2(1+1)桁目の数が2119の倍数であることを示しています。

a = 2019 * A + y
b = 2019 * B + y
a - b = 2019 * (A * B)
a - b は10のn乗です。
10と2019は互いに素であるので、a - b は2019の倍数になるからです。

そこで全ての余り計算し重複の数を数えることで、2019の倍数になる数を求めることができます。
さらに2019で割って余り0になる場合は、重複なしでも2019の場合になります。
以下の回答はTLEです。

S = list(input())
S.reverse()
amari = []
A = 0
c = 0
for i in range(len(S)):
    a = (int(A) + int(S[i]) *(10 ** i)) % 2019
    amari.append(a)
    if a == 0:
        c += 1
    A = a
print(c + len(amari) - len(set(amari)))