[PYTHON] Teilnahmebericht des AtCoder Sumitomo Mitsui Trust Bank Programmierwettbewerbs 2019

Teilnahmebericht des AtCoder Sumitomo Mitsui Trust Bank Programmierwettbewerbs 2019

A - November 30

Brechen Sie in 2 Minuten durch. Schreiben Sie einfach.

M1, D1 = map(int, input().split())
M2, D2 = map(int, input().split())

if D2 == 1:
    print(1)
else:
    print(0)

B - Tax Rate

Es brach in viereinhalb Minuten durch. Ich wusste nicht, was ich tun sollte, wenn es keine ganze Zahl wurde, und dann gab ich es richtig aus, aber es war AC.

N = int(input())

X = N / 1.08
if int(X) * 108 // 100 == N:
    print(int(X))
elif int(X + 1) * 108 // 100 == N:
    print(int(X + 1))
else:
    print(':(')

C - 100 to 105

Durchbruch in 7 ½ Minuten. WA1. Ich dachte, es sei schwieriger als das jüngste ABC C-Problem. WA war nicht, weil es schwierig war, sondern nur ein Chombo.

X = int(input())

dp = [0] * (X + 1 + 105)
dp[0] = 1

for i in range(X):
    if dp[i] == 1:
        for j in range(100, 106):
            dp[i + j] = 1
print(dp[X])

D - Lucky PIN

Es bricht in 22 Minuten und einer halben durch. Da es 3 Zeichen gibt, gibt es maximal 1000 Muster von 000 bis 999, also kann ich es mir leisten, alle Muster auszuprobieren, aber wenn N ≤ 30000 ist, scheint es TLE zu sein. Wenn also 4 oder mehr des gleichen Zeichens aufeinander folgen, sind es 3 Ich habe durch Komprimieren gesucht. Da sowieso nur 3 Zeichen verwendet werden, ist eine Folge von 4 oder mehr Zeichen bedeutungslos.

N = int(input())
S = input()

t = [S[0]]
p = S[0]
r = 1
for i in range(1, N):
    if S[i] == p:
        r += 1
        if r < 4:
            t.append(S[i])
    else:
        r = 1
        t.append(S[i])
T = ''.join(t)

result = 0
for i in range(10):
    a = T.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = T.find(str(j), a + 1)
        if b == -1:
            continue
        for k in range(10):
            if T.find(str(k), b + 1) != -1:
                result += 1
print(result)

Nachtrag: Ich musste es nicht komprimieren (^^; ich dachte, es gibt einen extremen Testfall, in dem es nach einer Reihe von ungefähr 30.000 Zeichen eine Fortsetzung gibt. Andernfalls wäre es kein D-Problem.

N = int(input())
S = input()

result = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = S.find(str(j), a + 1)
        if b == -1:
            continue
        for k in range(10):
            if S.find(str(k), b + 1) != -1:
                result += 1
print(result)

E - Colorful Hats 2

Durchbruch in 28 Minuten. WA1. Ich wollte nicht darauf vertrauen, dass A1 0 ist. Wenden Sie einfach die möglichen Muster von Anfang an an. E Einfach für Probleme.

N = int(input())
A = list(map(int, input().split()))

result = 1
t = [0, 0, 0]
for i in range(N):
    a = A[i]
    f = -1
    k = 0
    for j in range(3):
        if t[j] == a:
            k += 1
            if f == -1:
                t[j] += 1
                f = j
    result = (result * k) % 1000000007
print(result)

F - Interval Running

Ich konnte nicht durchbrechen. Aber als F-Problem ist es sehr einfach. Ich war enttäuscht, dass ich es verpasst habe, obwohl ich es zum ersten Mal abschließen konnte. Als ich die Erklärung sah, habe ich die Verarbeitung nur verpasst, als sie teilbar war.

from sys import exit

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

if A1 > B1:
    A1, B1 = B1, A1
    A2, B2 = B2, A2

if A2 < B2:
    print(0)
    exit()

if A1 * T1 + A2 * T2 < B1 * T1 + B2 * T2:
    print(0)
    exit()

if A1 * T1 + A2 * T2 == B1 * T1 + B2 * T2:
    print('infinity')
    exit()

a = B1 * T1 - A1 * T1
b = (A1 * T1 + A2 * T2) - (B1 * T1 + B2 * T2)
t = a // b

if a % b == 0:
    print(t * 2)
else:
    print(t * 2 + 1)