Codeforces Round #194 Div1D Characteristics of Rectangles

Codeforces

問題
N*Mの行列が与えられます。
この行列の端っこにある行や列をいくつか削ることができます（削らなくてもいいです）。

うまい削り方をして、結果として得られる新しい行列（部分長方形）の、「四隅の４つの値の最小値」を最大にした時の値を求めてください。

例えば、

1 1 1
1 2 2
1 2 2

の場合は1行目と1列目を削って
2 2
2 2
の最小値２というのが最大です。

制約

(2 ≤ n, m ≤ 1000)
(0 ≤ （行列の各要素の値） ≤ 10^9)


解法
答えは必ず行列内の要素のどれかの値になり、制約から高々10^9なので、
二分探索で「ある値lim以上の最小値を持つ削り方は存在するのか」というのを探していくというのが有力な選択肢です。

しかしこれを愚直に判定すると(nm)^2くらいの時間が掛かってしまうので工夫が必要です。
これを高速化するためにbool good[m][m]というメモを使います。
どういうメモかというと、good[r1][r2]は
「これまで見てきた行の中には、r1番目とr2番目が両方ともlim以上な行がどこかにある」
という意味です。
goodは最初全部falseですが、1回目にr1とr2番目が両方lim以上な行に訪れるとtrueになり、
2回目の行で訪れると、四隅がlim以上という部分長方形が作れることが示せます。

プログラムを見るとループが３つあって一見O(n^3)のコードに見えますが、
goodの更新が高々n^2回なので、n^2回未満でこのループは必ず抜け出します。

これによって二分探索と合わせてO(n^2logn)の解法が実現できます。


プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

li a[1010][1010];
li n,m;

bool check(li lim){
	bool good[1010][1010];
	rep(i,1010)rep(j,1010)good[i][j]=false;
	rep(i,n){
		vector<li> pos;
		rep(j,m){
			if(a[i][j]>=lim)pos.pb(j);
		}
		rep(j,sz(pos)){
			repp(k,j+1,sz(pos)){
				if(good[pos[j]][pos[k]])return true;
				good[pos[j]][pos[k]]=true;
			}
		}
	}
	return false;
}

int main(){
	cin>>n>>m;
	vector<li> aa;
	
	rep(i,n){
		rep(j,m){
			cin>>a[i][j];
			aa.pb(a[i][j]);
		}
	}
	
	sort(allof(aa));
	vector<li>::iterator it=unique(allof(aa));
	aa.erase(it,aa.end());
	
	//bin search
	li l=0, r=sz(aa)-1;
	li mid=(l+r)/2;
	li res=0;
	while(l<=r){
		mid=(l+r)/2;
		if(check(aa[mid])){
			res=aa[mid];
			l=mid+1;
		}
		else r=mid-1;
	}
	
	cout<<res<<endl;
	
	return 0;
}