AtCoder ABC #176 : E - Bomber

えらくFが難易度高かった回。
https://atcoder.jp/contests/abc176/tasks/abc176_e

問題

グリッド上M個のマスに爆破対象が設置されている。
どこかのマス（爆破対象があってもよい）を1つ指定し、爆弾を置くと、同じ列または同じ行にある爆破対象を破壊できるとする。
最適な場所に爆弾を置く場合、最大何個破壊できるか。

解法

まず、各列と行にある対象の個数を数え上げよう。
すると、爆破すべき列は最大個数の対象のある列のいずれかで、爆破すべき行は最大個数の対象のある行のいずれかである。
もし列と行を定めたとき、そのマスに爆破対象があると、破壊できる数は(列の対象数)+(行の対象数)-1であり、対象がないと(列の対象数)+(行の対象数)となる。
そこで、マスに爆破対象がないような列・行を探したい。

これは最大個数の対象がある列・行を総当たりしてしまえばよい。
そのまま愚直に行うとTLEするケースがあるが、マスに爆破対象があるのは高々M個なので、最大(M+1)を総当たりするうちに(列の対象数)+(行の対象数)となるマスがあれば見つかるので、途中で打ち切ればよい。

下記のコードは少し違うアプローチ。
総当たりしている点は同じだが、更新の可能性がない列・行は速めに打ち切っている。

int H,W,M;
int R[303030];
int C[303030];
set<pair<int,int>> S;
pair<int,int> PR[303030],PC[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>M;
	FOR(i,M) {
		cin>>y>>x;
		y--,x--;
		R[y]++;
		C[x]++;
		S.insert({y,x});
	}
	
	FOR(i,H) PR[i]={-R[i],i};
	FOR(i,W) PC[i]={-C[i],i};
	
	sort(PR,PR+H);
	sort(PC,PC+W);
	
	int ma=0;
	FOR(y,H) if(PR[y].first) {
		FOR(x,W) {
			int ty=-PR[y].first;
			int tx=-PC[x].first;
			if(ty+tx<=ma) break;
			if(tx==0) break;
			int cnt=ty+tx-(S.count({PR[y].second,PC[x].second}));
			ma=max(ma,cnt);
		}
	}
	
	cout<<ma<<endl;
	
}

まとめ

これ発音はボマーなのかボンバーなのか…元ネタを推測すると後者で良い？