No.165 四角で囲え!
- 座標圧縮+累積和+片側全探索+しゃくとり法/二分探索 で解く問題
- 累積和、座標圧縮とか久しぶりすぎて間違いまくった...。座標圧縮は c++ では insert 時に既にキーがあると insert されないので xmap.emplace(xs[i],xmap.size()) だけで ok
- 二分探索の上限 high を「とり得る最大値」にしてしまい、WAくらった...
pair<ll,ll> operator+(const pair<ll,ll> &a, const pair<ll,ll> &b) { return make_pair(a.first+b.first, a.second+b.second); } pair<ll,ll> operator-(const pair<ll,ll> &a, const pair<ll,ll> &b) { return make_pair(a.first-b.first, a.second-b.second); } class SurroundWithSquare { public: void solve(void) { int N,B; cin>>N>>B; // 座標圧縮を使う vector<ll> xs; vector<ll> ys; vector<tuple<ll,ll,ll>> ps; REP(i,N) { ll x,y,p; cin>>x>>y>>p; ps.emplace_back(x,y,p); xs.push_back(x); ys.push_back(y); } sort(RANGE(xs)); sort(RANGE(ys)); map<ll,int> xmap; map<ll,int> ymap; REP(i,N) { xmap.emplace(xs[i],xmap.size()); ymap.emplace(ys[i],ymap.size()); } const int maxX = xmap.size(); const int maxY = ymap.size(); // 0<=x,y<400 pair<ll,ll> field[maxY][maxX]; REP(y,maxY) REP(x,maxX) field[y][x] = make_pair(0,0); REP(i,N) { ll x,y,p; tie(x,y,p) = ps[i]; field[ymap[y]][xmap[x]] = make_pair(p,1); } pair<ll,ll> Sum[maxY+1][maxX+1]; // 累積和を計算する(レンジは半開区間) REP(y,maxY) REP(x,maxX) Sum[y+1][x+1] = field[y][x]; REP(y,maxY+1) REP(x,maxX) { Sum[y][x+1] = Sum[y][x+1] + Sum[y][x]; } REP(y,maxY) REP(x,maxX+1) { Sum[y+1][x] = Sum[y+1][x] + Sum[y][x]; } // 二分探索を使って高速化する O(N^3*log(N)) ll maxN = 0; REP(uy,maxY+1) REP(ly,uy+1) REP(lx,maxX+1) { int low = 0; int high = maxX-lx+1; ll n = 0; // ly,uy,lx を固定したとき cnt は ux に対して単調増加なので二分探索できる while (low+1 < high) { int mid = (low+high)/2; int ux = lx + mid; pair<ll,ll> cnt(0,0); cnt = Sum[uy][ux] - Sum[uy][lx] - Sum[ly][ux] + Sum[ly][lx]; if (cnt.first <= B) { low = mid; n = cnt.second; } else high = mid; } maxN = max(maxN, n); } cout<<maxN<<endl; } };
以下はしゃくとり法をつかった O(n^3) アルゴリズム
class SurroundWithSquare { public: void solve(void) { int N,B; cin>>N>>B; // 座標圧縮を使う vector<ll> xs; vector<ll> ys; vector<tuple<ll,ll,ll>> ps; REP(i,N) { ll x,y,p; cin>>x>>y>>p; ps.emplace_back(x,y,p); xs.push_back(x); ys.push_back(y); } sort(RANGE(xs)); sort(RANGE(ys)); map<ll,int> xmap; map<ll,int> ymap; REP(i,N) { xmap.emplace(xs[i],xmap.size()); ymap.emplace(ys[i],ymap.size()); } const int maxX = xmap.size(); const int maxY = ymap.size(); // 0<=x,y<400 pair<ll,ll> field[maxY][maxX]; REP(y,maxY) REP(x,maxX) field[y][x] = make_pair(0,0); REP(i,N) { ll x,y,p; tie(x,y,p) = ps[i]; field[ymap[y]][xmap[x]] = make_pair(p,1); } pair<ll,ll> Sum[maxY+1][maxX+1]; // 累積和を計算する(レンジは半開区間) REP(y,maxY) REP(x,maxX) Sum[y+1][x+1] = field[y][x]; REP(y,maxY+1) REP(x,maxX) { Sum[y][x+1] = Sum[y][x+1] + Sum[y][x]; } REP(y,maxY) REP(x,maxX+1) { Sum[y+1][x] = Sum[y+1][x] + Sum[y][x]; } ll maxN = 0; // 片側全探索・しゃくとり法 REP(uy,maxY+1) REP(ly,uy+1) { for (int lx = 0, ux = lx; ; ++lx) { for (; ux <= maxX; ++ux) { auto cnt = Sum[uy][ux] - Sum[uy][lx] - Sum[ly][ux] + Sum[ly][lx]; if (cnt.first > B) break; maxN = max(maxN, cnt.second); } if (ux >= maxX) break; } } cout<<maxN<<endl; } };