Codeforces #194 Div1 D. Characteristics of Rectangles

Div1D埋めも進めないとね。
http://codeforces.com/contest/333/problem/D

問題

N*Mの２次元グリッドの各セルに数値A[i][j]が振られている。
グリッドの価値とは、グリッドの四つ角の数値の最小値となる。
グリッドの上下左右を切り落として部分グリッドを作成できるとき、価値の最大値を求めよ。

解法

上下の切り落としをO(N^2)で総当たりする。
例えば残す最上位行をy1行、最下位行をy2行とする。
あとはmin(A[y1][x],A[y2][x])を各列について求め、１番目に大きい列と２番目に大きい列が端になるように左右を切り落とせば、min(A[y1][x],A[y2][x])のうち２番目のものが答えの候補となる。

全体でO(N^2*M)となるが、なんとか間に合う。

int H,W;
int A[1005][1005];

void solve() {
	int i,j,k,l,r,x,y,y1,y2; string s;
	
	cin>>H>>W;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	
	int ret=0;
	FOR(y1,H) for(y2=y1+1;y2<H;y2++) {
		int t1=0,t2=0;
		FOR(x,W) {
			r=min(A[y1][x],A[y2][x]);
			if(r>t2) {
				if(r>t1) t2=t1, t1=r;
				else t2=r;
			}
		}
		ret=max(ret,t2);
	}
	
	cout<<ret<<endl;
}

まとめ

Dにしては易しめな問題。