[PYTHON] AtCoderBeginnerContest176 Review & Summary (zweite Hälfte)

AtCoder ABC176 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 176, der am Samstag, den 22.08.2020, in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Die zweite Hälfte befasst sich mit dem E-Problem. Klicken Sie hier für die erste Hälfte Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

E Problem Bomber

Problemstellung Es gibt ein zweidimensionales Gitter aus $ H × W $ Quadraten. Darin befinden sich $ M $ Explosionsziele. Die Position der $ i $ -ten Explosion ist $ (h_i, w_i) $. Takahashi wählt ein $ 1 $ Quadrat, legt eine Bombe auf dieses Feld und detoniert es. Bombenziele, die sich in derselben Reihe oder Spalte wie die Bombe befinden, werden gesprengt. Sie können auch eine Bombe auf dem Platz platzieren, auf dem sich das Ziel der Explosion befindet. Takahashi versucht, die Anzahl der zu sprengenden Explosionsziele zu maximieren. Bitte teilen Sie uns mit, wie viele Explosionsziele Sie sprengen können.

Zum Zeitpunkt des Wettbewerbs habe ich falsch verstanden, dass das Ziel des Bombenangriffs eine Bombe war, und ich dachte, es sei eine Bomberman-ähnliche Geschichte und kämpfte. Unter der Annahme, dass die Anzahl der Explosionsziele in Zeile $ j $ $ Hcount_j $ und die Anzahl der Explosionsziele in Zeile $ k $ $ Wcount_k $ ist, beträgt die maximale Anzahl, die gesprengt werden kann, $ max (Hcount) + max (Wcount) $ oder Es ist entweder $ max (Hcount) + max (Wcount) -1 $.

Dies liegt daran, dass die zu installierende Kandidatenposition der Schnittpunkt der Zeile $ max (Hcount) $ und der Spalte $ max (Wcount) $ ist. Wenn sich an der Kreuzung ein Explosionsziel befindet, $ max (Hcount) + max ( Wcount) ―― 1 $ kann gesprengt werden. Wenn sich an der Kreuzung kein Explosionsziel befindet, kann $ max (Hcount) + max (Wcount) $ gesprengt werden. Suchen Sie also nach der Zielkreuzung und selbst wenn sich an der Kreuzung kein Explosionsziel befindet Sie können eine Antwort anfordern, je nachdem, ob sie vorhanden ist oder nicht.

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)

Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.