✨
ABC176 E - Bomber解説[python]
URL
制約
問題概要
- H*Wのグリッドがあり、Mこのマスにターゲットがある。
- １つのマスを選び、そのマスと同じ行、または列にあるターゲットの数を最大化したい。何個になるか？
提出コード
#!/usr/bin/env python3
import bisect
H, W, M = map(int, input().split())
row = [0] * (1 + H)
col = [0] * (1 + W)
match = []
for i in range(M):
h, w = map(int, input().split())
h -= 1
w -= 1
row[h] += 1
col[w] += 1
match.append(h * (10 ** 6) + w)
match.sort()
row, idx_r = zip(*sorted(zip(row, range(1 + H))))
col, idx_c = zip(*sorted(zip(col, range(1 + W))))
max_r = []
max_c = []
i = 0
while True:
if row[-i - 1] == row[-1]: # maxならそのindexをmax_r に追加する
max_r.append(idx_r[H - i])
else:
break
i += 1
i = 0
while True:
if col[-i - 1] == col[-1]:
max_c.append(idx_c[W - i])
else:
break
i += 1
# print(max_c, max_r, col, row, idx_c, idx_r)
match_flag = 1
for i in max_r:
for j in max_c:
if bisect.bisect_left(match, i * (10 ** 6) + j) == bisect.bisect_right(
match, i * (10 ** 6) + j
):
match_flag = 0
# print(match, i * (10 ** 6) + j, i, j)
break
print(col[-1] + row[-1] - match_flag)
考察
- 単純に行、列ごとにターゲットの数を数えて、行のmax + 列のmax をすれば良い
- もし、選んだ行、列の交点にターゲットがあれば-1する
実装方針
- 選んだ行、列の交点にターゲットがあルカの判定は3*10**5+1をかけたりして1次元の数字に落とす
- max になる行、列のindex はzip のsortとかで計算する。
次回への反省
- 計算量は？ Mが対角線上に並んでいるときなどがヤバくてO(M^2)かかる？ とりあえず投げたらACした。。
- 交点のみを探索しているので、M回以上探索すれば必ず一回は出てくる
- zip は使わなくてもmax を計算してからもう一度ループを回して
- 解説を読むと(h,w)の組でC++ のsetに入れて探索しているのでpythonのdictで処理するとよかった。
参考
Discussion