Ceci est un article de synthèse pour les débutants des professionnels de la compétition.
La solution que j'écris ici est écrite en regardant les commentaires et les soumissions d'autres personnes. Ce n'est peut-être pas ce que vous avez réellement soumis.
S mouton et loup loup, gagner est une question à se poser.
Si S est supérieur à W, le mouton ne sera pas attaqué.
S, W = map(int, input().split())
if S > W:
print('safe')
else:
print('unsafe')
Il s'agit de répondre à laquelle gagnera si la puissance d'attaque B avec la force physique A et la puissance d'attaque D avec la force physique C se touchent.
Takahashi-kun et Aoki-kun ont chacun besoin du nombre d'attaques arrondi à $ C / B $ et $ A / D $. Celui avec le plus petit nombre l'emporte. Aussi, si les chiffres sont les mêmes, Takahashi, qui peut être battu en premier, est avantageux.
Je l'ai implémenté avec l'idée ci-dessus. J'ai utilisé math.ceil () pour le processus de résumé. Si vous écrivez quelque chose comme (C + (B-1)) // B, vous n'avez pas besoin d'une bibliothèque.
import math
A, B, C, D = map(int, input().split())
if math.ceil(C/B) <= math.ceil(A/D):
print('Yes')
else:
print('No')
C'est un problème de compter le nombre de types de chaînes de caractères $ S_i $ saisies N fois.
Je l'ai mis dans un objet de type défini et j'ai compté la longueur.
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
Il s'agit de savoir combien de nombres peuvent être rendus divisibles d'ici 2019 lorsque le nombre d'entrée S est découpé dans une section arbitraire.
Je pensais que c'était un sujet similaire à this et j'ai écrit le code suivant. (En fait, je n'ai pas pu le faire pendant le concours parce que j'ai fait une erreur ou ne pouvais pas raccourcir le temps.)
import collections
S = input()
N = len(S)
M = [0]
mod = 0
ten = 1
for s in S[::-1]:
mod += (int(s) * ten) % 2019
mod %= 2019
M.append(mod)
ten *= 10
ten %= 2019
count = collections.Counter(M)
print(sum([c*(c-1)//2 for c in count.values()]))
Par exemple, s'il existe un nombre «1234567», ce processus calcule le surplus de «7», «67», «567», «4567», «34567», «234567» et «1234567», et le surplus correspond. S'il y a un certain nombre de chiffres, la section est divisible.
Dans le traitement réel, le temps de calcul est économisé en le divisant fréquemment et en effectuant le calcul de l'excédent.
Pour une explication mathématique détaillée, voir la question E dans article que j'ai écrit précédemment.
Le problème est de trouver l'itinéraire le plus court de la gare 1 à toutes les stations. Cependant, vous aurez besoin de pièces d'argent pour utiliser le train et vous devrez passer un temps différent à échanger de l'argent à chaque gare.
Jusqu'à présent, ABC n'a posé que la question E, mais c'est presque la première fois pour un problème de graphe solide. Je n'ai pas du tout compris et j'ai abandonné.
J'ai vu beaucoup d'explications et d'autres réponses.
Tout d'abord, en raison de la limite de 2 $ \ leq N \ leq 50 $, 1 $ \ leq A_i \ leq 50 $, le nombre total de pièces d'argent pouvant être transportées dans ce système est de 49 $ \ times50 = 2450 $. (Ce nombre peut être encore réduit en fonction de la valeur réelle de «N», «A», mais je vais expliquer avec ce nombre pour plus de commodité)
"Temps minimum $ T $ lors de la détention de pièces à la station n" est stocké dans le tableau suivant.
T[n][coins]
Vous pouvez le créer comme suit. Entrez une valeur suffisamment grande comme valeur initiale.
T = [[10**18 for _ in range(2451)] for _ in range(N)]
Les modèles de comportement possibles pour chaque station sont les feuilles de "coût cost, temps $ t $ pour aller à la station adjacente $ m $" "temps $ t $ pour utiliser des pièces d'or à la même station -Il n'y a pas d'autre choix que d'échanger contre des «coûts» (passez à $ m = n $ et pensez que vous avez consommé des «coûts» négatifs). Traitez ce comportement comme un taple.
(m, cost, t)
Enregistrez ce taple en tant que tableau pour chaque station $ n $.
act[n] = [(Action 1), (Action 2), (Action 3), ....]
Le code suivant stockera les valeurs entrées dans ces derniers.
N, M, S = map(int, input().split())
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
Puisque la recherche est effectuée à partir d'ici, l'état qui est la source de recherche est enregistré dans la file d'attente prioritaire. Traitez un état comme un taple. L'heure actuelle $ currentT $, la station actuelle $ n $ et le nombre de pièces d'argent en possession $ pièces $ sont exprimées comme suit.
(currentT, n, coins)
L'état initial de la file d'attente prioritaire est le suivant.
que = [(0, 0, S)]
Le tableau bidimensionnel "T" est rempli en extrayant de cette file d'attente dans l'ordre croissant de t et en effectuant une recherche. Enfin, si vous retirez la plus petite valeur de T [n], cela représente le temps minimum pour atteindre la station n.
Ensuite, le code écrit est le suivant.
from heapq import *
N, M, S = map(int, input().split())
T = [[10**18 for _ in range(2451)] for _ in range(N)]
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
que = [(0, 0, S)]
while que:
(currentT, n, coins) = heappop(que)
for m, cost, t in act[n]:
#Si "au montant que vous pouvez payer" "temps minimum T"[Destination][Argent de possession]Mettez à jour la valeur lorsque vous pouvez mettre à jour et ajoutez l'état à la file d'attente.
#Si le résultat de l'échange dépasse 2450, traitez-le comme 2450 et il n'y a pas de problème.
if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
T[m][min(2450, coins - cost)] = currentT + t
heappush(que, (currentT + t, m, min(2450, coins - cost)))
for i in range(1, N):
print(min(T[i]))
Il semble que ce soit un algorithme appelé la méthode Dyxtra. J'ai senti que c'était un problème difficile pour la question E, mais j'ai été surpris que l'algorithme de la partie de recherche finale soit extrêmement facile à écrire.
C'est tout pour cet article.
Recommended Posts