本番に一部しか参加できなかったので、本問は問題も見られず。
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求める系の問題をやっていたので、これ系がだいぶ典型に思えるようになった。