Official

F - Minimize Bounding Square Editorial by physics0523

この問題にはいくつかのヒントが用意されています。各項目をクリックすると内容を見ることができます。

ヒント1 この問題は、 $x$ 座標と $y$ 座標とを分離して考えることができます。
ヒント2 この問題では、ある貪欲法が成立します。
解説 各点の $x$ 座標の列を $X'$ 、$y$ 座標の列を $Y'$ とします。
これ以上点の移動が行えない時、描くべき正方形の一辺の長さの最小値は $\max(\max(X')-\min(X'), \max(Y')-\min(Y'))$ となります。
$\max$ に入った $2$ つの項 $\chi=\max(X')-\min(X')$ 、 $\gamma=\max(Y')-\min(Y')$ に関して場合分けします。
  • $\chi < \gamma$ の場合
    • $x$ 座標を変更しても最小化すべき値は変化しないのでいったん放置してよいです。 $y$ 座標に関して、 $\max(Y')$ と $\min(Y')$ のうち個数が少ない方を全て $1$ 変更(適切な方向に)できるならそうして $\gamma$ を $1$ 減らすべきで、できないならもう解を改善する余地はありません。
  • $\chi > \gamma$ の場合も同様です。
  • $\chi = \gamma$ の場合
    • この場合、 $\chi < \gamma$ とみなして $\gamma$ を先に $1$ 変更してもよければ、 $\chi,\gamma$ を同時に $1$ 変更するようにしても構いません。
重大な注意として、愚直に $1$ ずつ変更していては座標 $10^9$ の制約より実行時間制限に間に合わせるのは困難です。
この場合は、 $\min(X'), \max(X'), \min(Y'), \max(Y')$ の値が全体で高々 $2N$ 回しか変化しないことを念頭に置き、これらの値が変化するまでまとめて操作を行いましょう。
略証 まず、明らかに操作の過程で $\min(X')$ を小さくする / $\max(X')$ を大きくするべきではありません。これより、この両者を近づけていくような変更のみを考えます。
$\min(X')$ や $\max(X')$ は、動かせば動かすほど動かす必要のある点数が増えていきます。つまり、 $1$ 動かすのに必要なコストが(広義)単調増加していきます。
この性質から、 $\chi$ の値を決め打った時、上記の貪欲法に従わない動かし方から従う動かし方へと、点を動かす回数を増やさずにに変更できることが示せます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

int main(){
  long long n,k;
  cin >> n >> k;

  vector<long long> x(n),y(n);
  map<long long,long long> mx,my;
  for(long long i=0;i<n;i++){
    cin >> x[i] >> y[i];
    mx[x[i]]++;
    my[y[i]]++;
  }

  vector<pl> xv,yv;
  for(auto &nx : mx){
    xv.push_back(nx);
  }
  for(auto &nx : my){
    yv.push_back(nx);
  }

  long long xl=0,xr=xv.size()-1;
  long long yl=0,yr=yv.size()-1;

  while(k>0){
    long long gx=xv[xr].first-xv[xl].first;
    long long gy=yv[yr].first-yv[yl].first;

    long long fx,fy;
    long long hx,hy;
    long long cx,cy;
    if(gx!=0){
      if(xv[xl].second<xv[xr].second){
        hx=xv[xl+1].first-xv[xl].first;
        cx=xv[xl].second;
        fx=-1;
      }
      else{
        hx=xv[xr].first-xv[xr-1].first;
        cx=xv[xr].second;
        fx=1;
      }
    }
    if(gy!=0){
      if(yv[yl].second<yv[yr].second){
        hy=yv[yl+1].first-yv[yl].first;
        cy=yv[yl].second;
        fy=-1;
      }
      else{
        hy=yv[yr].first-yv[yr-1].first;
        cy=yv[yr].second;
        fy=1;
      }
    }

    if(gx==0 && gy==0){break;}
    else if(gx<gy){
      // shorten y
      long long opt=min({k/cy,hy,gy-gx});
      if(opt==0){break;}
      k-=cy*opt;
      if(fy==-1){yv[yl].first+=opt;}
      else{yv[yr].first-=opt;}
    }
    else if(gx>gy){
      // shorten x
      long long opt=min({k/cx,hx,gx-gy});
      if(opt==0){break;}
      k-=cx*opt;
      if(fx==-1){xv[xl].first+=opt;}
      else{xv[xr].first-=opt;}
    }
    else{
      // once x==y, let's keep it
      // shorten x&y
      long long opt=min({k/(cx+cy),hx,hy});
      if(opt==0){break;}
      k-=(cx+cy)*opt;

      if(fy==-1){yv[yl].first+=opt;}
      else{yv[yr].first-=opt;}
      
      if(fx==-1){xv[xl].first+=opt;}
      else{xv[xr].first-=opt;}
    }

    if(xl!=xr){
      if(xv[xl].first==xv[xl+1].first){
        xv[xl+1].second+=xv[xl].second;
        xl++;
      }
      else if(xv[xr].first==xv[xr-1].first){
        xv[xr-1].second+=xv[xr].second;
        xr--;
      }
    }
    if(yl!=yr){
      if(yv[yl].first==yv[yl+1].first){
        yv[yl+1].second+=yv[yl].second;
        yl++;
      }
      else if(yv[yr].first==yv[yr-1].first){
        yv[yr-1].second+=yv[yr].second;
        yr--;
      }
    }
  }

  {
    long long gx=xv[xr].first-xv[xl].first;
    long long gy=yv[yr].first-yv[yl].first;
    cout << max(gx,gy) << "\n";
  }
  return 0;
}

posted:
last update: