Google KickStart 2020H-C "Rugby"

これもやさし目なABC-Fって感じ　でも面白かった

codingcompetitions.withgoogle.com

問題概要

二次元グリッド上にN人の人がいる。N人をある格子点からX軸に平行に一列に並べたい。人が格子点から格子点に移動するためにかかるコストは2点のマンハッタン距離と等しい。終状態の列の位置と、人の並び順は任意とするとき、必要なコストの最小値は？ (N<=1e5 , 座標は絶対値1e9以下）

解法

「終状態の左端の人の座標」を考えましょう。X軸方向とY軸方向に分離して考えると、まず、Y座標は簡単に求められます。すなわち全員の座標をY軸昇順にソートして、その中央値にすればいいという有名なやつですね。

次に、X座標ですが、これはF(x) := 終状態の左端の人の座標がxの時、X軸平行成分のコストの総和 とした時、凸性がわかるので、3分探索をすれば求めることができます。実装は次の通りです。

editorialを見たらなんかO(NlogN)みたいなことが書いてあったので多分上と同じ方針だと思うんですがあまりに長いので読む気になっていません。"ternaly"みたいなワードがなかったので少し違うかも

追記 上手い解法を見つけた。Xの方をソートして、その後に添字分ずつ左にずらした時、終状態のX座標はずらした後のX座標の中央値にできる。なるほど...

youtu.be

// solution for KickStart 2020H-C
// author : lynmisakura
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 100010;

int N;
ll X[MAXN],Y[MAXN];

ll F(ll mid){
  ll res = 0;
  for (int i = 0; i < N; i++) {
    res += abs((mid + i) - X[i]);
  }
  return res;
}

ll get_x(){

  ll L = ll(-1e10);
  ll R = ll(1e10);
  
  while(R - L > 2){
    
    ll RR = (L + R * 2) / 3;
    ll LL = (L * 2 + R) / 3;
    
    if(F(LL) < F(RR)){
      R = RR;
    }else{
      L = LL;
    }

  }
  
  return F((R + L) / 2);

} 

ll get_y(){

  ll mid;

  if (N % 2 == 0) {
    mid = (Y[(N/2)] + Y[(N/2)-1]) / 2;
  } else {
    mid = Y[(N / 2)];
  }

  ll res = 0;
  for (int i = 0; i < N; i++) {
    res += abs(Y[i] - mid);
  }

  return res;
}

void main2(){

  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  sort(X,X+N);
  sort(Y,Y+N);

  cout << get_x() + get_y() << '\n';

}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(20);

  int tt;cin >> tt;
  for(int i=1;i<=tt;i++){
    cout << "Case #" << i << ": ";
    main2();
  }
}