Official

F - Minimize Bounding Square Editorial by physics0523

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

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

実装例 (C++):

Copy
  1. #include<bits/stdc++.h>
  3. using namespace std;
  4. using pl=pair<long long,long long>;
  6. int main(){
  7.   long long n,k;
  8.   cin >> n >> k;
  10.   vector<long long> x(n),y(n);
  11.   map<long long,long long> mx,my;
  12.   for(long long i=0;i<n;i++){
  13.     cin >> x[i] >> y[i];
  14.     mx[x[i]]++;
  15.     my[y[i]]++;
  16.   }
  18.   vector<pl> xv,yv;
  19.   for(auto &nx : mx){
  20.     xv.push_back(nx);
  21.   }
  22.   for(auto &nx : my){
  23.     yv.push_back(nx);
  24.   }
  26.   long long xl=0,xr=xv.size()-1;
  27.   long long yl=0,yr=yv.size()-1;
  29.   while(k>0){
  30.     long long gx=xv[xr].first-xv[xl].first;
  31.     long long gy=yv[yr].first-yv[yl].first;
  33.     long long fx,fy;
  34.     long long hx,hy;
  35.     long long cx,cy;
  36.     if(gx!=0){
  37.       if(xv[xl].second<xv[xr].second){
  38.         hx=xv[xl+1].first-xv[xl].first;
  39.         cx=xv[xl].second;
  40.         fx=-1;
  41.       }
  42.       else{
  43.         hx=xv[xr].first-xv[xr-1].first;
  44.         cx=xv[xr].second;
  45.         fx=1;
  46.       }
  47.     }
  48.     if(gy!=0){
  49.       if(yv[yl].second<yv[yr].second){
  50.         hy=yv[yl+1].first-yv[yl].first;
  51.         cy=yv[yl].second;
  52.         fy=-1;
  53.       }
  54.       else{
  55.         hy=yv[yr].first-yv[yr-1].first;
  56.         cy=yv[yr].second;
  57.         fy=1;
  58.       }
  59.     }
  61.     if(gx==0 && gy==0){break;}
  62.     else if(gx<gy){
  63.       // shorten y
  64.       long long opt=min({k/cy,hy,gy-gx});
  65.       if(opt==0){break;}
  66.       k-=cy*opt;
  67.       if(fy==-1){yv[yl].first+=opt;}
  68.       else{yv[yr].first-=opt;}
  69.     }
  70.     else if(gx>gy){
  71.       // shorten x
  72.       long long opt=min({k/cx,hx,gx-gy});
  73.       if(opt==0){break;}
  74.       k-=cx*opt;
  75.       if(fx==-1){xv[xl].first+=opt;}
  76.       else{xv[xr].first-=opt;}
  77.     }
  78.     else{
  79.       // once x==y, let's keep it
  80.       // shorten x&y
  81.       long long opt=min({k/(cx+cy),hx,hy});
  82.       if(opt==0){break;}
  83.       k-=(cx+cy)*opt;
  85.       if(fy==-1){yv[yl].first+=opt;}
  86.       else{yv[yr].first-=opt;}
  87.       
  88.       if(fx==-1){xv[xl].first+=opt;}
  89.       else{xv[xr].first-=opt;}
  90.     }
  92.     if(xl!=xr){
  93.       if(xv[xl].first==xv[xl+1].first){
  94.         xv[xl+1].second+=xv[xl].second;
  95.         xl++;
  96.       }
  97.       else if(xv[xr].first==xv[xr-1].first){
  98.         xv[xr-1].second+=xv[xr].second;
  99.         xr--;
  100.       }
  101.     }
  102.     if(yl!=yr){
  103.       if(yv[yl].first==yv[yl+1].first){
  104.         yv[yl+1].second+=yv[yl].second;
  105.         yl++;
  106.       }
  107.       else if(yv[yr].first==yv[yr-1].first){
  108.         yv[yr-1].second+=yv[yr].second;
  109.         yr--;
  110.       }
  111.     }
  112.   }
  114.   {
  115.     long long gx=xv[xr].first-xv[xl].first;
  116.     long long gy=yv[yr].first-yv[yl].first;
  117.     cout << max(gx,gy) << "\n";
  118.   }
  119.   return 0;
  120. }
#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:

2025-04-27 (Sun)
13:54:32 +00:00