AtCoderBeginnerContest176 Review & Summary (second semestre)

AtCoder ABC176 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 176, qui s'est tenu le samedi 22/08/2020, dans l'ordre du problème A, en tenant compte. La seconde moitié traite du problème E. Cliquez ici pour la première moitié 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

E problème Bomber

Énoncé du problème Il existe une grille bidimensionnelle de carrés $ H × W $. Il y a des cibles d'explosion de $ M $ dans ce domaine. La position du $ i $ ème souffle est $ (h_i, w_i) $. Takahashi choisit un carré de 1 $, pose une bombe sur ce carré et le fait exploser. Les cibles de bombardement qui se trouvent dans la même ligne ou colonne que la bombe exploseront. Vous pouvez également placer une bombe sur la case où se trouve la cible de l'explosion. Takahashi essaie de maximiser le nombre de cibles à exploser. Veuillez nous dire combien de cibles de tir vous pouvez faire sauter.

Au moment du concours, j'ai mal compris que la cible du bombardement était une bombe, et j'ai pensé que c'était une histoire de type Bomberman, alors j'ai eu du mal. En supposant que le nombre de cibles d'explosion à la ligne $ j $ est $ Hcount_j $ et que le nombre de cibles d'explosion à la ligne $ k $ est $ Wcount_k $, le nombre maximum pouvant être dynamité est $ max (Hcount) + max (Wcount) $ ou C'est soit $ max (Hcount) + max (Wcount) -1 $.

En effet, la position candidate à installer est l'intersection de la ligne $ max (Hcount) $ et de la colonne $ max (Wcount) $, et s'il y a une cible d'explosion à l'intersection, $ max (Hcount) + max ( Wcount) ―― 1 $ peut être dynamité, et s'il n'y a pas de cible d'explosion à l'intersection, $ max (Hcount) + max (Wcount) $ peut être dynamité, alors recherchez l'intersection cible et même un cas où il n'y a pas de cible d'explosion à l'intersection Vous pouvez demander une réponse selon qu'il y en a une ou non.

abc176e.py


h, w, m = map(int, input().split())
bom_set = set()
h_dict = {}
w_dict = {}
for i in range(m):
    hh, ww = map(int, input().split())
    bom_set.add(tuple([hh, ww]))
    if hh in h_dict:
        h_dict[hh] += 1
    else:
        h_dict[hh] = 1
    if ww in w_dict:
        w_dict[ww] += 1
    else:
        w_dict[ww] = 1
h_max_count = max(h_dict.values())
w_max_count = max(w_dict.values())
hh_dict = {}
ww_dict = {}
for hh in h_dict:
    if h_dict[hh] == h_max_count:
        hh_dict[hh] = h_max_count
for ww in w_dict:
    if w_dict[ww] == w_max_count:
        ww_dict[ww] = w_max_count
flag = 0
for hh in hh_dict:
    for ww in ww_dict:
        if tuple([hh, ww]) not in bom_set:
            flag = 1
            break
    if flag == 1:
        break
if flag == 1:
    print(h_max_count + w_max_count)
else:
    print(h_max_count + w_max_count - 1)

Merci d'avoir lu la seconde moitié jusqu'à la fin.

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 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)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest174 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)
AtCoderBeginnerContest180 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é