Edit

【pythonでABC176を解説】E - Bomber

問題概要

問題ページ

E - Bomber
E - Bomber

問題ページへ移動する

問題文

\(H \times W\) マスの二次元グリッドがあります。この中には \(M\) 個の爆破対象があります。 \(i\) 個目の爆破対象の位置は \(\left(h_i, w_i \right)\)です。

高橋君は \(1\) つのマスを選び、そのマスに爆弾を設置し、起爆します。爆弾と同じ行または同じ列に存在する爆破対象が爆破されます。爆破対象が存在するマスに爆弾を設置することも出来ます。

高橋君は、爆破する爆破対象の数を最大化しようとしています。最大でいくつの爆破対象を爆破出来るか答えてください。

制約

  • 入力は全て整数
  • \(1 \leq H, W \leq 3 \times 10^5\)
  • \(1 \leq M \leq \min\left(H\times W, 3 \times 10^5\right)\)
  • \(1 \leq h_i \leq H\)
  • \(1 \leq w_i \leq W\)
  • \(\left(h_i, w_i\right) \neq \left(h_j, w_j\right) \left(i \neq j\right)\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(int)
    hl = [0] * h
    wl = [0] * w
    for _ in range(m):
        hv, wv = list(map(int, input().rstrip('\n').split()))
        hl[hv-1] += 1
        wl[wv-1] += 1
        d[hv-1, wv-1] += 1
    h_max = 0
    h_tar = []
    for i in range(h):
        if h_max == hl[i]:
            h_tar.append(i)
        elif h_max < hl[i]:
            h_max = hl[i]
            h_tar = [i]
    w_max = 0
    w_tar = []
    for i in range(w):
        if w_max == wl[i]:
            w_tar.append(i)
        elif w_max < wl[i]:
            w_max = wl[i]
            w_tar = [i]
    for hv in h_tar:
        for wv in w_tar:
            if (hv, wv) not in d:
                print(w_max + h_max)
                exit()
    print(w_max + h_max - 1)


if __name__ == '__main__':
    solve()

-Edit
-