AtCoder ABC167 Ceci est un résumé des problèmes de AtCoder Beginner Contest 167, qui s'est tenu le 2020-05-10 (dimanche), dans l'ordre du problème A, en tenant compte de la considération. Le premier semestre traite des problèmes jusqu'à ABCD. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Takahashi essaie de s'inscrire en tant que membre d'un certain service Web. J'ai d'abord essayé d'enregistrer l'ID en tant que $ S $. Cependant, cet ID était déjà utilisé par un autre utilisateur. Par conséquent, M. Takahashi a envisagé d'enregistrer une chaîne de caractères avec des caractères $ 1 $ ajoutés à la fin de $ S $ en tant qu'ID. Takahashi essaie d'enregistrer un nouvel identifiant en tant que $ T $. Déterminez si cela remplit les conditions ci-dessus.
Je pense que ce domaine peut être résolu sans aucun problème s'il s'agit de python.
Je pense que vous pouvez écrire t [: -1] comme t [: len (t) -1].
Dans les deux cas, vous pouvez créer une chaîne de caractères excluant le dernier caractère de la chaîne de caractères.
abc167a.py
s = input()
t = input()
if s == t[:-1]:
print("Yes")
else:
print("No")
Énoncé du problème Il existe des cartes $ A $ avec 1 $, des cartes $ B $ avec 0 $ et des cartes $ C $ avec -1 $. Lorsque vous choisissez seulement $ K $ parmi ces cartes, quelle est la valeur maximale possible en tant que somme des nombres inscrits sur les cartes que vous avez choisies?
Afin d'augmenter la valeur possible, nous avons choisi une carte avec 1 $ le plus possible, et avons considéré qu'il fallait éviter de choisir au maximum -1 $.
--Si le nombre de cartes que vous devez sélectionner est de $ A $ ou moins, vous pouvez sélectionner la carte avec 1 $ écrit dessus, la valeur maximale est donc de $ K $.
Tout ce que vous avez à faire est d'implémenter le branchement conditionnel avec l'instruction if.
abc167b.py
a, b, c, k = map(int, input().split())
if a >= k:
print(k)
elif a + b >= k:
print(a)
else:
print(a - (k - (a + b)))
J'ai pu résoudre le problème B en environ 6 minutes, donc je pense que je peux le résoudre dans mon temps idéal.
Énoncé du problème Takahashi, qui a commencé la programmation compétitive, a $ M $ d'algorithmes qu'il veut apprendre. Au départ, la compréhension de chaque algorithme est de 0 $. Lorsque Takahashi est allé à la librairie, $ N $ d'ouvrages de référence étaient en vente. Le $ i $ ème livre de référence $ (1 \ leq i \ leq N) $ est vendu pour $ C_i $ yen, et en achetant et en lisant, chaque $ j (1 \ leq j \ leq M) $ Augmente la compréhension de l'algorithme $ j $ th de $ A_ {i, j} $. De plus, vous ne pouvez améliorer votre compréhension d'aucune autre manière. L'objectif de Takahashi est d'améliorer la compréhension de tous les algorithmes $ M $ à $ X $ ou plus. Déterminez si Takahashi peut atteindre l'objectif et, si possible, calculez le montant minimum requis pour atteindre l'objectif.
La contrainte est petite, $ 1 \ leq N, M \ leq 12 $. Il y a deux façons d'acheter le livre de référence $ N $, "acheter" ou "ne pas acheter", et il y a un total de 2 $ ^ N $, donc vous pouvez le résoudre en cherchant tout. Je pensais que j'utilisais souvent des fonctions récursives lors de la recherche de tout. En regardant les résultats de soumission d'autres "AC", étonnamment, il y avait de nombreux codes qui n'utilisaient pas de fonctions récursives. J'ai utilisé une fonction récursive pour créer un vecteur (par exemple, $ [1, 0, 1, 1] $) indiquant quel livre acheter et utilisé numpy pour calculer la matrice. Le code que j'ai soumis a reçu chaque ligne une fois dans une liste et l'a divisé en une liste de montants et de compréhension, mais sur Twitter "Je peux le recevoir comme ça." C, * a = map (int, int, Seule la partie qui reçoit la valeur est modifiée en se référant à la description "input (). Split ())` ".
abc167c.py
import numpy as np
def func(ans, b_list, a_list, c_list, k, x):
if k == 0:
b_list = np.asarray(b_list)
x_list = np.dot(b_list, a_list)
if np.all(x_list >= x):
return np.inner(c_list, b_list)
else:
return ans
ans = min(ans, func(ans, b_list + [1], a_list, c_list, k - 1, x))
ans = min(ans, func(ans, b_list + [0], a_list, c_list, k - 1, x))
return ans
n, m, x = map(int, input().split())
c_list = []
a_list = []
for i in range(0, n):
c, *a = map(int, input().split())
c_list.append(c)
a_list.append(a)
ans = float("inf")
c_list = np.asarray(c_list)
a_list = np.asarray(a_list)
ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))
if ans == float("inf"):
print(-1)
else:
print(ans)
Récemment, je sens que j'ai du mal à résoudre le problème de la recherche complète (sueur) Même si je comprends toutes les recherches, la mise en œuvre prend trop de temps, je dois donc m'entraîner pour pouvoir écrire intelligemment.
Énoncé du problème Il y a des villes $ N $ dans le royaume de Takahashi. Les villes sont numérotées de 1 $ à $ N $. Chaque ville a des téléporteurs à 1 $. Le téléporteur de la ville $ i (1 \ leq i \ leq N) $ est redirigé vers la ville $ A_i $. Le roi Takahashi aime l'entier positif $ K $. Le roi égoïste Takahashi veut savoir dans quelle ville il arrivera s'il part d'une ville de 1 $ et utilise le téléporteur seulement $ K $ fois. Créez un programme pour cela pour le roi Takahashi.
Personnellement, j'ai trouvé que c'était plus facile que le problème C. En particulier, j'ai un fort sentiment d'être sauvé par l'exemple (j'ai tout de suite remarqué qu'il bouclait).
Exemple d'entrée 2
6 7272022141732493516 5 2 5 3 2
Dans l'exemple d'entrée 2, à partir de la ville $ 1 $,
~ Politique ~
Puisque la liste de programmation (tableau) commence à 0, vous devez faire attention à cela, mais j'ai pensé que ce ne serait pas si difficile à implémenter si vous faisiez attention, donc le code suivant a été soumis en premier.
abc167d.py
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
if next_machi in machi_list:
break
count += 1
machi_list.append(next_machi)
machi = next_machi
next_machi = x[machi] - 1
z = 0
for i in range(0, count):
if machi_list[i] == next_machi:
z = i
break
loop_machi_list = machi_list[z:]
if k < z:
machi = machi_list[k] + 1
print(machi)
else:
k = k - z
machi = loop_machi_list[k % len(loop_machi_list)] + 1
print(machi)
Cependant, le code ci-dessus a un temps d'exécution lent, et j'obtiens "TLE" et le désespoir. Je me demande si l'algorithme est faux, y a-t-il un moyen de le rendre plus rapide? J'étais confus. Cependant, je ne pouvais pas penser à une meilleure méthode, alors j'ai senti qu'il y avait un problème avec la mise en œuvre et je l'ai revue.
Accroché peut-être à la paille, je doutais que dans l'instruction for ʻif next_machi in machi_list: `(il y a une valeur similaire dans la liste) C'était la partie qui faisait (je vérifie). C'était une mauvaise décision. Lorsque le tableau est devenu grand, j'ai pensé qu'il faudrait du temps pour tout vérifier, j'ai donc préparé un dict immédiatement. Après avoir réécrit le code comme ci-dessous, il a passé "AC" en toute sécurité.
abc167d.py
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = {}
while True:
if next_machi in machi_dict:
break
count += 1
machi_dict[next_machi] = 1
machi_list.append(next_machi)
machi = next_machi
next_machi = x[machi] - 1
z = 0
for i in range(0, count):
if machi_list[i] == next_machi:
z = i
break
loop_machi_list = machi_list[z:]
if k < z:
machi = machi_list[k] + 1
print(machi)
else:
k = k - z
machi = loop_machi_list[k % len(loop_machi_list)] + 1
print(machi)
Ce "TLE" résonne avec le classement, donc je voulais acquérir la puissance minimale d'implémentation ici étant donné que j'utiliserai python dans le futur au travail. Les algorithmes que j'ai appris dans le concours pro sont les emplois dans lesquels je serai impliqué dans le futur, et cela semble fort probable sans eux, mais c'est très éducatif de pouvoir expérimenter des exemples lourds avec des implémentations aussi détaillées (relations de liste, etc.) En particulier).
C'est la fin du premier semestre.
Le classement momentané lorsque j'ai fini de résoudre le problème D était plutôt bon, mais ce n'était pas bon après cela, donc j'ai besoin d'étudier un peu plus. Merci d'avoir lu jusqu'à la fin du premier semestre.
La seconde moitié expliquera le problème EF. Prévu pour continuer dans la seconde moitié.
Recommended Posts