AtCoderBeginnerContest176 Review & Summary (second half)

AtCoder ABC176 This is a summary of the problems of AtCoder Beginner Contest 176, which was held on Saturday, 2020-08-22, in order from problem A, taking into consideration the consideration. The second half deals with the E problem. Click here for the first half The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

E problem Bomber

Problem statement There is a 2D grid of $ H × W $ squares. There are $ M $ blast targets in this. The position of the $ i $ th blast is $ (h_i, w_i) $. Takahashi chooses a $ 1 $ square, places a bomb on that square, and detonates it. Bomb targets that are in the same row or column as the bomb will be blown up. You can also place a bomb on the square where the bomb target exists. Takahashi is trying to maximize the number of blast targets to blast. Please tell us how many blast targets you can blast.

At the time of the contest, I misunderstood that the target of the bomb was a bomb, and thought it was a Bomberman-like story, so I struggled. Assuming that the number of blast targets in line $ j $ is $ Hcount_j $ and the number of blast targets in line $ k $ is $ Wcount_k $, the maximum number that can be blasted is $ max (Hcount) + max (Wcount) $ or It is either $ max (Hcount) + max (Wcount) -1 $.

This is because the candidate position to install is the intersection of the row that is $ max (Hcount) $ and the column that is $ max (Wcount) $, and if there is a blast target at the intersection, $ max (Hcount) + max ( Wcount) ―― 1 $ can be blasted, and if there is no blast target at the intersection, $ max (Hcount) + max (Wcount) $ can be blasted, so search for the target intersection and even one case where there is no blast target at the intersection You can ask for an answer depending on whether or not there is one.

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)

Thank you for reading the second half to the end.

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest161 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest168 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (first half)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half