ABC176 E - Bomber (500)
全ての点を調べるのは
$ O(HW)
でTLE
縦と横でそれぞれいくつ爆弾があるかを数え、最も多い爆弾を持つ行と列のリストを作る
最大の破壊できる数は
$ 最も多い行の爆弾 + 最も多い列の爆弾
かそれから1引いたもの
選ぶべき爆破地点は最も多い爆弾を持つ行と列が交わるところ
その地点に爆弾がなければその地点が最大値
全ての交差地点に爆弾があればどの点でも最大値
最悪
$ O(HW)
のようだが爆弾は
$ M
個なので
$ O(H+W+M)
で解けるため間に合う
問題:
https://atcoder.jp/contests/abc176/tasks/abc176_e
提出:
https://atcoder.jp/contests/abc176/submissions/16127605
#ABC176
#500pt
#E
#ABC
#AtCoder