Ich konnte nur bis zu D rechtzeitig lösen. .. .. Danach googelte ich und bezog mich auf die Codes anderer Leute und beendete das Rennen mit F.

A Vergleichen Sie den Teil der Zeichenfolge T ohne das letzte Zeichen mit S.

# A

S = input()
T = input()
T = T[:len(S)]
print('Yes' if T == S else 'No')

B Nimm so viele A-Karten wie möglich, dann B so viele wie möglich und C, wenn du K immer noch nicht erreichen kannst.

# B

A, B, C, K = list(map(int, input().split()))

score = 0
if K <= A:
    score = K
    print(score)
    exit()

score += A
K -= A
if K <= B:
    print(score)
    exit()

K -= B
print(score - K)

C Da die maximale Anzahl von Mustern $ 2 ^ {12} = 4096 $ beträgt, ist es genug Zeit, alle Muster mit Python zu überprüfen. Sehr verrückter Code.

# C

N, M, X = list(map(int, input().split()))
CAs = [list(map(int, input().split())) for i in range(N)]

import numpy as np
Cs = np.array([ca[0] for ca in CAs])
As = [np.array(ca[1:]) for ca in CAs]

import itertools
states = list(itertools.product([True, False], repeat=N))

def compute(state):
    arr = np.array([0] * M)
    for i in range(N):
        arr += As[i] * state[i]
    price = (Cs * state).sum() if ((arr >= X).sum() == M) else -1
    return price


res = np.array(list(map(compute, states)))
res = res[res > 0]
print(min(res) if len(res) > 0 else -1)

D Es gibt immer eine Schleife. Überprüfen Sie daher die Größe der Schleife und subtrahieren Sie den entsprechenden Betrag von der Häufigkeit, mit der Sie den Teleporter $ K $ verwenden. Dieser richtige Abzug dauerte lange und ich konnte mich nicht mit dem E-Problem befassen. .. ..

# D

N, K = list(map(int, input().split()))
As = list(map(int, input().split()))

def compute(city, K):
    for i in range(K):
        city = As[city-1]
    print(city)

cities_visited = [False] * N
i = 0
city = 1
city_visited_time = {}

while not cities_visited[city - 1]:
    cities_visited[city - 1] = True
    city_visited_time[city-1] = i
    city = As[city-1]
    i += 1

loop_start = city_visited_time[city-1]
loop_end = i


div = (K - loop_start) // (loop_end - loop_start)
if K - loop_start < 0 or div == 0:
    compute(1, K)
else:
    compute(city, K - loop_start - div * (loop_end - loop_start))

E Die Zielfunktion ist wie folgt.

\sum_{n=0}^K M (M-1) ^{N-1-n} {}_{N-1} C _n

$ n $ ist die Anzahl benachbarter Paare von Blöcken derselben Farbe. Wenn beispielsweise $ n = 0 $ ist, sind die Farben aller benachbarten Blöcke unterschiedlich. In diesem Fall kann der Block ganz links gemäß $ M $ frei ausgewählt werden, und der rechte Block muss anders als links ausgewählt werden, damit $ M-1 $ ausgewählt werden kann. Berücksichtigt man dies für alle Blöcke, $ n = Wenn es 0 $ ist, wird es $ M (M-1) ^ {N-1} $. Wenn $ n = 1 $ ist und eine Menge zusammen betrachtet wird, kann dies auf die gleiche Weise berechnet werden, wie wenn $ n = 0 $ für $ N-1 $ Blöcke berücksichtigt wird.

Wenn die Zielfunktion so berechnet wird, wie sie ist, wird sie zu TLE oder MLE. Daher verwende ich den Satz von Fermat als Technik (Referenzlink).

# E

N, M, K = list(map(int, input().split()))
p = 998244353

comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p
    
print(res)

F Bitte schauen Sie sich das Kommentarvideo so an, wie es ist. .. .. Ersetzen Sie (,) durch ± Zahlen und notieren Sie die Summe und das Minimum für jede Abfrage. Woran man denken sollte

Ob die Summe aller positiven Summen gleich der Summe aller negativen Summen ist
Ob es unterwegs 0 nicht überschreitet

Letzteres ist beispielsweise ())) ((Eine Abfrage wie (die Summe ist +1, aber der Mindestwert ist -2), sodass Sie keine Klammerzeichenfolge ohne zwei oder mehr (links) erstellen können.

# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append((min_state, state))
    else:
        list_minus.append((min_state - state, -state))

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Impressionen

Ich habe append ((min_state, state)) im F-Problemcode verwendet, aber als ich append ([min_state, state]) verwendet habe, wurde es TLE. Es gab eine Beschreibung in Kapitel 3 von High Performance Python, aber es war eine gute Gelegenheit zu erkennen, dass sich die Geschwindigkeit erheblich ändern wird.

Löse AtCoder 167 mit Python

Impressionen