kmjp's blog

競技プログラミング参加記です

yukicoder : No.165 四角で囲え!

本番に一部しか参加できなかったので、本問は問題も見られず。
Codeforcesとかでよく出そうな問題。
http://yukicoder.me/problems/264

問題

2次元座標上にN個の異なる格子点の座標(X[i],Y[i])が与えられる。
また、各点には得点P[i]が振られている。

これらの点を軸に平行な長方形で囲いたい。
長方形内の格子点の合計得点がB以下な範囲で、頂点数を最大化せよ。

解法

まずX座標・Y座標をともに座標圧縮してしまおう。
次に、まず左右の境界を総当たりで定める。
たとえば下記のコードは長方形の左端をx1、右端をx2としている。
この状態で、尺取り法の要領で上端y1と下端y2を定めていく。

まずy2をインクリメントし、Y[i]==y2かつx1≦X[i]≦x2となる頂点を長方形内にあると判定し、頂点数及び得点を加算する。
このとき得点がBを超えた場合、尺取り法の要領で得点がBを切るまで上端y1を増やしていく。
その際Y[i]==y1かつx1≦X[i]≦x2となる頂点は長方形外に出た判定し、頂点数及び得点を減算する。
このように尺取り法をしながら、得点B以下の時の最大頂点数を求めればよい。
計算量はO(N^3)なので、yukicoderなら余裕で間に合う。

int N;
ll B;
map<int,int> MX,MY;
int X[500],Y[500],P[500];
vector<pair<int,int> > D[500];
int ma=0;

void solve() {
	int i,j,k,l,r,x1,x2,y1,y2; string s;
	
	cin>>N>>B;
	FOR(i,N) cin>>X[i]>>Y[i]>>P[i], MX[X[i]]=MY[Y[i]]=0;
	MX[-1000000001]=MY[-1000000001]=0;
	MX[1000000001]=MY[1000000001]=0;
	x1=y1=0;
	ITR(it,MX) it->second=x1++;
	ITR(it,MY) it->second=y1++;
	FOR(i,N) D[MY[Y[i]]].push_back(make_pair(MX[X[i]],P[i]));
	
	FOR(x2,MX.size()) FOR(x1,x2+1) {
		int num=0;
		ll tot=0;
		y1=0;
		FOR(y2,MY.size()) {
			ITR(it,D[y2]) if(it->first>=x1 && it->first<=x2) num++, tot+=it->second;
			while(tot>B) {
				ITR(it,D[y1]) if(it->first>=x1 && it->first<=x2) num--, tot-=it->second;
				y1++;
			}
			ma=max(ma,num);
		}
	}
	
	cout<<ma<<endl;
	
}

まとめ

Codeforcesでsubmatrix求める系の問題をやっていたので、これ系がだいぶ典型に思えるようになった。