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.
A - Coffee C'est un problème de déterminer si les 3ème et 4ème caractères d'une chaîne de caractères donnée sont les mêmes, et les 5ème et 6ème caractères sont les mêmes.
Le code suivant est implémenté tel quel. C'est acceptable.
s = input()
if s[2] == s[3] and s[4] == s[5]:
print('Yes')
else: print('No')
B - Golden Coins
Si vous échangez le montant d'argent donné n et le convertissez en 1000 pour chaque boule de 500 yens et 5 pour chaque boule de 5 yens, quelle est la valeur maximale? C'est le problème.
Le nombre de balles de 500 yens est «n // 500», et le nombre de balles de 5 yens est «n% 500 // 5».
Je l'ai implémenté comme suit.
n = int(input())
print(n//500*1000 + n%500//5*5)
C - Traveling Salesman around Lake Compte tenu de la localisation des maisons qui existent autour du lac, il s'agit de considérer la distance à parcourir pour faire le tour de toutes les maisons sur le trajet le plus court.
La position de l'extrémité nord du lac a été fixée à 0, et les positions des maisons ont été stockées dans le réseau pendant deux tours dans le sens des aiguilles d'une montre à partir de là. En partant de l'une des maisons du premier tour, nous avons calculé la distance pour faire le tour de toutes les maisons et calculé la valeur maximale.
K, N = map(int, input().split())
A = list(map(int, input().split()))
A += [a+K for a in A]
minD = 1e6
for n in range(N):
minD = min(minD, A[n+N-1] - A[n])
print(minD)
La manière d'écrire était différente dans le commentaire. Le lac en fait presque tout sauf une partie. La partie qui ne passe pas se situe entre les maisons les plus éloignées.
Je l'ai un peu réécrit. C'est plus beau.
K, N = map(int, input().split())
A = list(map(int, input().split()))
A.append(A[0]+K)
maxD = 0
for n in range(N+1):
maxD = max(maxD, A[n+1] - A[n])
print(K-maxD)
Postscript: python peut prendre un index négatif comme li [-1], il n'est donc pas nécessaire d'augmenter le tableau.
D - Line++
C'est un problème d'obtenir la distribution de la longueur de chemin la plus courte à partir d'un graphique donné.
Il existe une bibliothèque appelée networkx qui peut gérer la théorie des graphes en python. C'est une bibliothèque très pratique qui peut obtenir chaque paramètre à partir de la création d'un graphe. Calculons maintenant la distribution.
import networkx as nx
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
out = [0] * N
G = nx.Graph()
G.add_nodes_from(list(range(N)))
G.add_edges_from([(i, i+1) for i in range(N-1)] + [(X, Y)])
for i in range(N-1):
for j in range(i+1, N):
out[nx.shortest_path_length(G, i, j)] += 1
for i in range(1, N):
print(out[i])
Eh bien, je ne peux pas utiliser cette bibliothèque avec atcoder.
Je ne pouvais pas du tout étudier l'exploration de graphes, alors j'ai abandonné et suis passé au problème suivant.
J'ai vu le commentaire. Ce problème ne semble pas nécessiter de recherche difficile. Il n'y a que deux choix pour la distance du point A au point B: BA (en procédant un par un) ou ʻabs (AX) + 1 + abs (BY)` (en passant par le raccourci de XY). Il n'y en a pas. Le plus court de ces deux est l'itinéraire le plus court.
Ainsi, le code suivant est une réécriture du code ci-dessus uniquement pour la méthode de recherche d'itinéraire la plus courte.
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
out = [0] * N
for i in range(N-1):
for j in range(i+1, N):
out[min(j-i, abs(i-X)+1+abs(j-Y))] += 1
for i in range(1, N):
print(out[i])
Je suis passé par là.
E - Red and Green Apples Vous recevrez une pomme rouge avec un délicieux $ p_i $, une pomme verte avec un délicieux $ q_i $ et une pomme incolore avec un délicieux $ r_i $. C'est un problème de trouver le goût maximum en mangeant X pommes rouges et Y pommes vertes. La clé est de savoir comment gérer les pommes incolores.
Prenez X des pommes rouges par ordre de délicatesse et Y des pommes vertes par ordre de délicatesse. Tout ce que vous avez à faire est de remplacer les pommes X + Y par celles qui ne sont pas délicieuses avec des pommes incolores.
X, Y, A, B, C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))
P.sort()
Q.sort()
R.sort()
out = P[-X:] + Q[-Y:]
out.sort()
for i in range(min(C, X+Y)):
if R[-i-1] > out[i]:
out[i] = R[-i-1]
else:
break
print(sum(out))
Avec cela, j'ai pu le résoudre avec une marge dans le temps de calcul.
C'est tout pour cet article.
Recommended Posts