AtCoderBeginnerContest176復習＆まとめ（後半）

AtCoder ABC176

2020-08-22(土)に行われたAtCoderBeginnerContest176の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではE問題を扱います．前半はこちら
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

E問題　Bomber

問題文
$H×W$マスの二次元グリッドがあります。この中には$M$個の爆破対象があります。
$i$個目の爆破対象の位置は$(h_i,w_i)$です。
高橋君は$1$つのマスを選び、そのマスに爆弾を設置し、起爆します。爆弾と同じ行または同じ列に存在する爆破対象が爆破されます。爆破対象が存在するマスに爆弾を設置することも出来ます。
高橋君は、爆破する爆破対象の数を最大化しようとしています。最大でいくつの爆破対象を爆破出来るか答えてください。

コンテスト本番時は，爆破対象を勝手に爆弾だと勘違いして，ボンバーマン的な話かと思って苦戦してしまいました．
行$j$の爆破対象の個数を$Hcount_j$,行$k$の爆破対象の個数を$Wcount_k$とすると，最大で爆破出来る数は，$max(Hcount) + max(Wcount)$ または， $max(Hcount) + max(Wcount) - 1$のいずれかである．

なぜなら，設置する位置の候補は，$max(Hcount)$となる行と，$max(Wcount)$となる列の交点であり，交点に爆破対象があれば，$max(Hcount) + max(Wcount) - 1$爆破でき，交点に爆破対象がなければ，$max(Hcount) + max(Wcount)$爆破できるため，対象となる交点を探索し，交点に爆破対象がない場合が一つでもあるかどうかで答えを求めることができる．

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)

後半も最後まで読んでいただきありがとうございました．