PythonでABC176 Eを解く

はじめに

昨日のABCで解けなかったE - Bomberをやります。

E - Bomber

gridを二次元配列で保持すると管理が面倒なのと時間が厳しいので、$H,W$それぞれの軸で爆弾の数を管理します。
$H,W$軸でそれぞれの爆弾の数の最大値を選んで、それぞれの最大値の和を返せば正解になりそうですが、それだけだと不十分です。これだと、交差している点に爆弾がある場合に対応できていないからです。交差している点に爆弾があるときは、それぞれの最大値の和-1になります。

交差している点はdictにtupleを入れて保持します。0は爆弾が無い点、1は爆弾がある点です。

from collections import defaultdict

h, w, m = map(int, input().split())

cnt_h = [0] * h
cnt_w = [0] * w
dic = defaultdict(int)

for _ in range(m):
    h_m, w_m = map(int, input().split())
    cnt_h[h_m - 1] += 1
    cnt_w[w_m - 1] += 1
    dic[(h_m - 1, w_m - 1)] += 1

max_h = max(cnt_h)
max_w = max(cnt_w)

mh = []
mw = []

for i in range(h):
    if max_h == cnt_h[i]:
        mh.append(i)

for i in range(w):
    if max_w == cnt_w[i]:
        mw.append(i)

flag = False
for i in mh:
    for j in mw:
        if dic[(i, j)] == 0:
            flag = True #0の点があるならそれが最大値になるのでbreakします。
            break
    if flag:
        break

if flag:
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)