Je ne pouvais résoudre que jusqu'à D à temps. .. .. Après cela, j'ai cherché sur Google et j'ai fait référence aux codes des autres et j'ai terminé la course à F.

A Comparez la partie de la chaîne T excluant le dernier caractère avec S.

# A

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

B Prenez autant de cartes A que vous pouvez, puis B autant que vous le pouvez et C si vous ne pouvez toujours pas atteindre K.

# 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 Puisque le nombre maximum de modèles est de 2 $ ^ {12} = 4096 $, il est suffisant de vérifier tous les modèles avec python. Code très fou.

# 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 Il y a toujours une boucle, alors vérifiez la taille de la boucle et soustrayez le montant approprié du nombre de fois où vous utilisez le téléporteur $ K $. Cette déduction appropriée a pris du temps et je n'ai pas pu entrer dans le problème E. .. ..

# 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 La fonction objectif est la suivante.

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

$ n $ est le nombre de paires adjacentes de blocs de la même couleur. Par exemple, si $ n = 0 $, les couleurs de tous les blocs adjacents seront différentes. Dans ce cas, le bloc le plus à gauche peut être sélectionné librement en fonction de $ M $, et le bloc de droite doit être sélectionné différemment de la gauche, de sorte que $ M-1 $ peut être sélectionné. En considérant cela pour tous les blocs, $ n = Quand il vaut 0 $, il devient $ M (M-1) ^ {N-1} $. Lorsque $ n = 1 $, si un ensemble est considéré ensemble, il peut être calculé de la même manière que lorsque $ n = 0 $ est considéré pour des blocs $ N-1 $.

Si la fonction objectif est calculée telle quelle, elle devient TLE ou MLE. Par conséquent, j'utilise le théorème de Fermat comme technique (lien de référence).

# 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 Veuillez regarder la vidéo du commentaire tel quel. .. .. Remplacez (,) par ± nombres et enregistrez la somme et le minimum pour chaque requête. À quoi penser

Si la somme de toutes les sommes positives est égale à la somme de toutes les sommes négatives -S'il ne dépasse pas 0 sur le chemin

Ce dernier est, par exemple, ())) ((Une requête comme (la somme est +1 mais la valeur minimale est -2, donc vous ne pouvez pas créer une chaîne de parenthèses sans deux ou plus (à gauche).

# 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')

Impressions

Quand j'ai utilisé append ((min_state, state)) dans le code du problème F, j'ai obtenu TLE lorsque j'ai utilisé append ([min_state, state]). Il y avait une description de cela dans le chapitre 3 de Python haute performance, mais c'était une bonne occasion de se rendre compte que la vitesse changera considérablement.

Résolvez AtCoder 167 avec python

Impressions