AtCoder Beginner Contest 176, E : Bomber

問題文

　https://atcoder.jp/contests/abc176/tasks/abc176_e

問題概要

　$H \times W$ のグリッド上に，$M $ 個のオブジェクトがある．$i$ 番目のオブジェクトは座標 $( y_i, x_i )$ にある．オブジェクトの座標はユニークである．
　ここで，ある一つの位置を選び，そこに爆弾を設置し，起爆する．爆弾が爆発すると，爆弾と同じ行・同じ列にあるオブジェクトが破壊される*1．オブジェクトと同じ位置に設置してもよい．
　最大でいくつのオブジェクトを破壊できるか？

制約

• $1 \leq H, W \leq 3 \times 10^5$
• $M \leq M \leq \min( H \times W, 3 \times 10^5 )$

解法

　ある位置に爆弾を置いたときに爆破できるオブジェクトの数は，

• オブジェクトの無い位置に爆弾を設置すると，行にある個数 + 列にある個数
• オブジェクトのある位置に爆弾を設置すると，行にある個数 + 列にある個数 - 1

となります．後者の -1 は，爆弾を置いた位置にあるオブジェクトをダブルカウントすることを防ぐためです．
　行・列について大体独立なので，基本的には，オブジェクトがたくさんある行・列をそれぞれ選んでその位置に爆弾を置くと多くのオブジェクトを壊すことができます．行または列にある個数が最大でないような行・列を選んで爆弾を置いた場合を考えてみると，爆破できるオブジェクトの個数は，最大値をとる行・列を選んだ場合における，上の箇条書きの下側の値を超えられません．従って，爆弾を置くとすれば，最も多くのオブジェクトがある行・列をそれぞれ選ぶのがよいです．
　あとは -1 されるかどうかの判定ができれば問題を解くことができます．-1 されないためには，前述のように，オブジェクトが無い位置に爆弾を設置すればよいです．そのような位置があるかどうかは，オブジェクトの個数が最大になる行・列だけを取り出してきた部分空間と，そこに乗っているオブジェクトの個数を比較することで判定できます．オブジェクトの個数 $<$ 部分空間の広さ であれば，鳩ノ巣原理より，オブジェクトの無い位置が存在します．

コード

int main()
{
	IN( int, H, W, M );
	VI Y( M ), X( M );
	REP( i, M )
	{
		cin >> Y[i] >> X[i];
		--Y[i], --X[i];
	}

	VI counts_y( H ), counts_x( W );
	REP( i, M )
	{
		++counts_y[ Y[i] ];
		++counts_x[ X[i] ];
	}

	const int max_y = *max_element( ALL( counts_y ) );
	const int max_x = *max_element( ALL( counts_x ) );

	VI ys, xs;
	REP( y, H )
	{
		if ( counts_y[y] == max_y )
		{
			ys.PB( y );
		}
	}
	REP( x, W )
	{
		if ( counts_x[x] == max_x )
		{
			xs.PB( x );
		}
	}

	int inner = 0;
	REP( i, M )
	{
		if ( binary_search( ALL( ys ), Y[i] ) && binary_search( ALL( xs ), X[i] ) )
		{
			++inner;
		}
	}

	cout << max_y + max_x - ( inner == LL( SZ( ys ) ) * SZ( xs ) ) << endl;

	return 0;
}

*1:貫通するボンバーマン的なこと