AtCoder ABC173 Ceci est un résumé des problèmes de AtCoder Beginner Contest 173, qui s'est tenu le 2020-07-05 (dimanche), dans l'ordre du problème A, en tenant compte de la considération. La première moitié traite des problèmes jusqu'à ABC. 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 Achetez des articles $ N $ Yen au magasin. Combien cela coûte-t-il de changer en payant avec des factures de 1000 $ yens seulement? Cependant, le paiement doit être effectué avec le nombre minimum requis de billets de 1000 $ yens.
Je pensais pouvoir calculer le changement en utilisant les trois derniers chiffres du $ N $ yen, alors j'ai calculé le reste en divisant $ N $ par 1000 $. Vous pouvez obtenir le résultat souhaité en soustrayant le reste de 1 000 $, mais dans le cas de 1 000 $ x x $ yen, le changement est à l'origine de 0 $ yen, mais le reste est de 0 $, donc le résultat devient «1000». Parce que ça finit, j'ai fait une branche conditionnelle avec l'instruction if. Dans la solution de la considération, j'ai pensé que la méthode de calcul sans branchement conditionnel était écrite.
abc173a.py
n = int(input())
k = n % 1000
if k == 0:
print(0)
else:
print(1000 - k)
Énoncé du problème M. Takahashi a participé au concours de programmation AXC002 et soumis le code à la question A. Il existe des cas de test $ N $ pour ce problème. Pour chaque cas de test $ i (1 \ leq i \ leq N) $, la chaîne $ S_i $ représentant le résultat du juge est donnée, donc le résultat du juge est "AC", "WA", "TLE", "RE" Veuillez trouver le nombre de ceux qui l'étaient. Pour le format de sortie, reportez-vous à la colonne de sortie.
J'ai honnêtement mis la contribution dans le dict.
abc173b.py
n = int(input())
key_dict = {"AC": 0, "WA": 0, "TLE": 0, "RE": 0}
for i in range(n):
key = input()
key_dict[key] += 1
print("AC x " + str(key_dict["AC"]))
print("WA x " + str(key_dict["WA"]))
print("TLE x " + str(key_dict["TLE"]))
print("RE x " + str(key_dict["RE"]))
Je veux pouvoir écrire comme le code python du commentaire officiel.
abc173b.py
N = int(input())
s = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
print('{0} x {1}'.format(v, s.count(v)))
Énoncé du problème Il y a une grille de cellules dans la ligne $ H $ et la colonne $ W $. La couleur de la cellule de la ligne $ i $ à partir du haut et de la colonne $ j $ à partir de la gauche $ (1 \ leq i \ leq H, 1 \ leq j \ leq W) $ est donnée comme caractère $ c_ {i, j} $ Quand $ c_ {i, j} $ est ".", Il est blanc, et quand il est "#", il est noir. Pensez à faire ce qui suit: ・ Sélectionnez quelques lignes (peut être une ligne de 0 $) et quelques colonnes (peut être une colonne de 0 $). Ensuite, peignez toutes les cellules de la ligne sélectionnée et les cellules de la colonne sélectionnée en rouge. Compte tenu de l'entier positif $ K $. Combien de lignes et de colonnes peuvent être sélectionnées pour qu'il ne reste plus que $ K $ de cellules noires après l'opération? Ici, les deux choix sont considérés comme différents lorsqu'il y a des lignes ou des colonnes qui ne sont choisies que dans une.
Je pensais que je devais faire une recherche complète, alors je l'ai résolu en utilisant une fonction récursive, mais la mise en œuvre a pris beaucoup de temps.
abc173c.py
import numpy as np
def funk(matrix, n, k, no_list, h, w):
if n == 0:
mask = np.ones((h, w))
for i in range(h):
if no_list[i] == 1:
mask[i,] = 0
for j in range(w):
if no_list[h+j] == 1:
mask[:,j] = 0
if np.sum(matrix * mask) == k:
return 1
else:
return 0
ans = 0
ans += funk(matrix, n - 1, k, no_list + [1], h, w)
ans += funk(matrix, n - 1, k, no_list + [0], h, w)
return ans
ans = 0
h, w, k = map(int, input().split())
n = h + w
matrix = np.zeros((h, w))
for i in range(h):
line = input()
for j in range(w):
if line[j] == "#":
matrix[i,j] = 1
else:
matrix[i,j] = 0
no_list = []
ans += funk(matrix, n, k, no_list, h, w)
print(ans)
C'est la fin du premier semestre. Récemment, le commentaire officiel a été décrit très soigneusement, donc j'espère que vous pourrez vous y référer pour la solution détaillée. Merci d'avoir lu jusqu'à la fin du premier semestre.
La seconde moitié expliquera le problème DEF. Suite dans la seconde moitié.
Recommended Posts