Täglicher AtCoder # 52 in Python

Einführung

Letztes Mal Heute werde ich 3 Fragen von AGC-A lösen.

** Gedanken ** Ich habe die Idee verstanden, konnte sie aber nicht umsetzen. Sei $ a $ eine Liste von $ [0] * (n + 1) $. Ich konnte es nicht implementieren, weil ich versucht habe, sowohl '<' als auch '>' zusammen zu behandeln. N ist auch ungefähr $ 5 * 10 ^ 5 $, also wird $ O (2N) (Berechnungsbetrag ignoriert den Koeffizienten) $ passieren. Zuerst von '<' verarbeiten. Wenn $ s [i] == '<' $ ist, wird $ a [i + 1] $ zu $ a [i] + 1 $. Als nächstes werden wir '>' verarbeiten, aber ein gewisser Einfallsreichtum ist erforderlich. '>' Muss wegen der Ungleichung von hinten berechnet werden. Multiplizieren Sie also den Bereich (n) mit umgekehrt. Wenn $ s [i] == '>' $, nimm $ a [i] = max (a [i + 1] + 1, a [i]) $. Nehmen Sie zum Schluss $ sum (a) $.

s = list(input())
n = len(s)

a = [0] * (n+1)
for i in range(n):
    if s[i] == '<':
        a[i+1] = a[i]+1
for i in reversed(range(n)):
    if s[i] == '>':
        a[i] = max(a[i+1]+1,a[i])
print(sum(a))

AGC015-A

** Gedanken ** Da $ N = 10 ^ 9 $ ist, wird $ O (N) $ nicht passieren. $ n = 1 $ → 1 wenn $ a = b $, 0 wenn $ a \ neq b $. Außerdem ist es 0, wenn $ a $> $ b $ und 1, wenn $ a $ = $ b $. Betrachten Sie die anderen Fälle. Die Mindestsumme ist nicht, wenn $ a * n $. Dies liegt daran, dass der Maximalwert nicht $ b $ erreicht, wenn alle $ a $ sind. Daher wird es $ a (n-1) + b $. Ebenso ist die maximale Summe $ b (n-1) + a $. Sie können alles von $ a (n-1) + b $ bis $ b (n-1) + a $ machen. Daher beträgt die Anzahl der Summen $ b (n-1) + a- {a (n-1) + b} + 1 $. Wenn Sie dies berechnen, können Sie es in $ (b-a) (n-2) + 1 $ umwandeln. Es kann berechnet werden, ohne die Formel zu transformieren, aber es wurde transformiert, weil es sauber sein sollte.

n, a, b = map(int,input().split())

if n == 1:
    if a == b:
        print(1)
    else:
        print(0)
elif a >= b:
    if a == b:
        print(1)
    else:
        print(0)
else:
    ans = (b-a)*(n-2)+1
    print(ans)

AGC006-A

** Gedanken ** Da $ N $ klein genug ist, suchen Sie in der Reihenfolge $ s oder t $ nach $ N $, um den Maximalwert zu finden, den es in der anderen enthält.

n = int(input())
s = input()
t = input()

c = 0
for i in range(n):
    d = t[:i]
    if d in s:
        c = i
if s == t: #Sie können früher schreiben und den for-Prozess überspringen
    print(n)
else:
    print(2*n-c)

Zusammenfassung

Warum hat AGC-A einen schwierigen Eindruck? Beim ABC dieser Woche wird es braun sein. Wir sehen uns wieder, gute Nacht.