Überprüfung des Atcoders ABC158 bis Frage E (Python)

3/14 Aufgrund des Kommentars korrigiert. Vielen Dank.

Competitive Pro Ein Anfänger hat begonnen, an Atcoder teilzunehmen, daher werde ich einen Artikel zum Lernen schreiben. Klicken Sie hier für die Wettbewerbe, an denen Sie teilgenommen haben. [AtCoder Beginner Contest 158] (https://atcoder.jp/contests/abc158)

Die Sprache wird Python sein. Der Zweck ist eine Überprüfung, es ist also nicht die Lösung, die ich tatsächlich gefunden habe. Ich schreibe, indem ich mir Erklärungen und andere Antworten ansehe. A - Station and Bus Wird eine Zeichenkette als Stationsinformation angegeben und enthält sie zwei Arten von Stationen, Firma A und Firma B? Ist das Problem.

In der eigentlichen Einreichung habe ich ehrlich gesagt die Zeichenfolge gedreht, um zu sehen, ob sie eine andere Station enthält. In diesem Fall werden nur drei Zeichenfolgen angegeben, sodass Sie sie einfach vergleichen können.

s = input()
if s[0] == s[1] or s[1] == s[2]: print('No')
else: print('Yes')

B - Count Balls Wenn Sie eine feste Anzahl von blauen und roten Kugeln setzen, wie viele Blautöne enthält ein bestimmter Punkt? Ist das Problem.

Ehrlich gesagt, als ich versuchte, es für zu drehen, war die Berechnungszeit vorbei. Endlich wird mir klar, dass es kein solches Spiel ist. Ich habe es mit einem viel schmutzigen Code als unten eingereicht.

N, A, B = map(int, input().split())
out = N // (A + B) * A
rem = min(N % (A + B), A)
print(out + rem)

Nachdem ich die Erklärung gesehen hatte, dachte ich, dass die Restberechnung bequem ist, wenn man die verbleibende Zahl findet.

C - Tax Increase Gibt es einen Stückpreis von A Yen mit dem ermäßigten Steuersatz und B Yen ohne diesen? Ist das Problem.

Um den Berechnungsbereich einzugrenzen, stellen Sie zuerst die Minimal- und Maximalwerte ein, die die Bedingung von A erfüllen, und prüfen Sie dann, ob die Bedingung von B in diesem Bereich erfüllt ist. Die Angabe dieses Bereichs war umständlich, und obwohl ich mich auf der arithmetischen Ebene befand, war ich verwirrt und durcheinander.

import math
A, B = map(int, input().split())
minV = math.ceil(A / 0.08)
maxV = (A + 1) // 0.08
for i in range(minV, maxV):
    if int(i * 0.1) == B:
        print(i)
        exit()
print(-1)

Bei diesem Problem ist die Einstellung eines engen Bereichs von $ 1 \ leq A, B \ leq 100 $ jedoch von Anfang an klar angegeben, so dass es anscheinend gut war, gehorsam von 1 aus zu suchen. Da der Berechnungsbetrag O (n) ist, ist es viel besser, als mit zusätzlichen Dingen zu verstopfen.

A, B = map(int, input().split())
maxV = 1010 #Ein höherer Wert als dieser erfüllt niemals die Bedingung B.
for i in range(1, maxV):
    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        exit()
print(-1)

D - String Formation Es ist ein Problem, die Zeichenfolge gemäß dem angegebenen Befehl zu ändern.

Ich habe das Folgende auf einfache Weise geschrieben. Ich habe eine solche Antwort eingereicht und die Berechnungszeit war abgelaufen.

s = input()
n = int(input())
for i in range(n):
    Q = input().split()
    if Q[0] == '1':
        s = s[::-1]
    else:
        if Q[1] == '1':
            s = Q[2] + s
        else:
            s = s + Q[2]
print(s)

Der Erklärung zufolge scheint es einige Zeit zu dauern, bis jede Operation die Zeichenfolge invertiert. Anstatt es tatsächlich umzudrehen, sollten Sie Informationen darüber aufbewahren, ob es umgedreht wird oder nicht. Da das Hinzufügen zum Anfang des Arrays einige Zeit in Anspruch nimmt, scheint es auch erforderlich zu sein, das Ende des Arrays hinzuzufügen.

Aus diesem Grund habe ich eine Variable isReverse hinzugefügt, die angibt, ob sie invertiert ist. Es wurde die Variable top hinzugefügt, in der die Informationen am Anfang gespeichert werden, sodass es immer der "Prozess zum Hinzufügen am Ende" der Zeichenfolge ist.

s = input()
top = ''
n = int(input())
isReverse = False
for i in range(n):
    Q = input().split()
    if(Q[0] == '1'):
        isReverse = not isReverse
    else:
        if Q[1] == '1':
            if isReverse: s += Q[2]
            else: top += Q[2]
        else:
            if isReverse: top += Q[2]
            else: s += Q[2]
if isReverse: s = s[::-1] + top
else: s = top[::-1] + s
print(s)

Sie können es jetzt rechtzeitig tun.

E - Divisible Substring

Die Frage ist, wie viele Intervalle in einer gegebenen Folge von Zahlen durch $ p $ teilbar sind.

Das habe ich eingereicht. Ich habe alle Sequenzen überprüft und $ O (n ^ 2) $ berechnet, und natürlich war die Zeit vorbei.

n, p = map(int,input().split())
s = input()
count = 0
for i in range(n):
    for j in range(1, n - i + 1):
        num = int(s[i: i + j])
        if num % p == 0:
            count += 1
print(count)

Dies scheint mathematische Techniken zu erfordern. Ich habe das Kommentarvideo gesehen, weil es schwierig war, den Kommentar zu lesen.

Nummerieren Sie zunächst die angegebene Zeichenfolge von rechts.

D = [d_N, d_{N - 1}, \cdots, d_1, d_0]

Der Wert, der durch Multiplizieren jedes Werts mit $ 10 ^ i $ erhalten wird, ist der Wert, den Sie tatsächlich verarbeiten möchten.

D' = [d_N\times 10^N, d_{N - 1}\times 10^{N- 1}, \cdots, d_1\times 10, d_0]

Betrachten Sie den Rest der Division von $ p $ für jede Anzahl von Ziffern. "Beim Teilen durch 2" und "beim Teilen durch 5" sind jedoch ausgeschlossen, da sie den Multiplikator von 10 stören. Daher werden wir die Fälle klassifizieren. (i) Für $ p \ neq 2, 5 $

M = [(d_N\times 10^N)\% p, (d_{N - 1}\times 10^{N- 1})\% p, \cdots, (d_1\times 10)\% p, (d_0)\% p]

Lassen Sie uns den erhaltenen Restterm als $ m_i $ ausdrücken. $ M = [m_N, m_{N - 1}, \cdots, m_1, m_0]$ Die Summe der Zahlen von 0 bis zur i-ten Ziffer $ V_i $ ist $ V_i = \sum^i_{k = 0} d_i \times 10^i $ Es kann von gefunden werden. Der Rest $ s_i , der durch Teilen dieser Zahl durch p erhalten wird, ist $ s_i = (\sum^i_{k = 0} m_i) % p $ Es kann von gefunden werden. Lassen Sie uns dies in ein paar Spalten schreiben. $ S = [s_N, s_{N - 1}, \cdots, s_1, s_0]$$ Wenn Sie das Intervall ausschneiden, in dem dieses $ s_i $ übereinstimmt, ist dies ein Wert, der durch $ p $ geteilt werden kann. Sie müssen also nur die Anzahl der Kombinationen zählen. Da die Ziffern, die $ s_i = 0 $ erfüllen, so wie sie sind teilbar sind, wird auch die Zahl gezählt.

(ii) Wenn $ p = 2, 5 $

Die durch 2 teilbare Zahl und die durch 5 teilbare Zahl können bestimmt werden, indem nur die letzte Ziffer betrachtet wird. Sie können erhalten werden, indem alle möglichen Kombinationen summiert werden (n Wege, wenn die Zahl die n-te Ziffer von links ist), wenn die Zahl, die die Bedingung erfüllt, auf die erste Ziffer gesetzt ist.

Um dies jedoch noch schneller zu machen, gilt das Verteilungsgesetz der Restberechnung

ab \mod c = (a \mod c)(b\mod c)\mod c

Wird auch verwendet, um den Rest für $ 10 ^ i $ zu berechnen. Ich habe dies nicht bemerkt (oder weil ich das Gesetz der Überschussberechnung nicht kannte), und selbst wenn ich mir die Antwortbeispiele anderer Leute ansah, trat TLE häufig auf.



n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

Ich werde den Artikel vorerst abschließen. Wenn ich Zeit habe, möchte ich auch Frage F hinzufügen.