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