AtCoderBeginnerContest173 Review & Summary (First Half)

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

Problème A Paiement

É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)

Résumé du statut du juge du problème B

É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)))

Problème C H et 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

AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
Résumé du didacticiel Django Girls Première moitié
AtCoder Revue des questions précédentes (première moitié de 12 / 8,9)